Description

In a mystery city, the train station looks like the picture below. 

Each train cabin only can come from the A side and leave through side B.

Suppose that each train cabin can be separated from the others cars before entering the station, and can also leave the station alone through side B.

Since the IDs of the cabins coming from side A are in increasing order, i.e., 1, 2, …, n, not all leaving sequences are possible for those cabins.

For example, if there are 3 cabins, [2 1 3] is achievable, but [3 1 2] is not.

 

Given n train cabins and the leaving sequence, your task is to determine whether the leaving sequence is possible.

If you are implementing your algorithm with stacks or queues, please design them by yourself. 

Note that the <stack>, <queue>, <vector> and <list> are not allowed.

 

Input

The input starts with a number n (1≤n≤100000), indicating that there are n train cabins 1, 2, …, n entering from side A, followed by a sequence containing n distinct numbers, ranging from 1 to n.

 

Output

"YES" or "NO", note that all alphabets are uppercase letters.

YES indicates the sequence is possible; NO means the given sequence is impossible.

You need to output '\n' at the end of the line.

(newline)

Sample Input  Download

Sample Output  Download

Tags

Discuss