Description

There is a train station with a railway layout as shown in the diagram. Each train enters from direction A and exits from direction B, while its carriages can be reorganized.
Assume that the train arriving from direction A has n carriages (n ≤ 1000), numbered sequentially as 1, 2, 3, ..., n.
Before entering the station, the carriages are not connected to each other, and they can move independently onto the track at point B. Additionally, the station C can hold any number of carriages. However, once a carriage enters station C, it cannot return to the track in direction A, and once it enters the track in direction B, it cannot return to station C.

The staff responsible for carriage scheduling need to determine whether it is possible to arrange the carriages in the specified order a1, a2, ..., an when exiting from direction B. Please verify if the specified carriage order can be achieved.

Input Format

The first line contains an integer n (n ≤ 1000), indicating the number of carriages. The second line contains n numbers, representing the specified carriage order.

Output Format

If the specified carriage order can be achieved, output the string "YES"; otherwise, output "NO" (note: uppercase letters, without quotes).

5
5 4 3 2 1

YES

Hint

Analysis: Upon observation, it is discovered that the entire scheduling process essentially simulates the push and pop operations of a stack. During this process, we can categorize the numbers into three states: pre-stack, in-stack, and post-stack. We can observe that when a number is popped from the stack, any number smaller than it must have either already been popped or still be in the stack—it cannot be in the pre-stack state. Additionally, the numbers in the stack must be in descending order when viewed from the top to the bottom of the stack. For example, if 5 is popped, then the numbers 1, 2, 3, and 4 must have either been popped before 5 or still be in the stack (e.g., if 1, 3, and 4 are in the stack, they should appear from top to bottom as 4, 3, 1). They cannot be in the pre-stack state.

If a number is to be popped, all numbers currently in the stack must be smaller than it; otherwise, it would contradict the properties of the stack, making the sequence invalid. Therefore, we can solve the problem as follows: Starting from the first number, scan the sequence where a[i] represents the current number to be popped. If there exists a number larger than a[i] still in the stack, a contradiction arises, and we output "NO". Otherwise, mark the current number a[i] as post-stack. Then, for the numbers in the range [1, a[i]-1] that have not been popped, mark them as in-stack. Specifically, we can use the following state representations: 0 for undetermined state, 1 for in-stack state, and 2 for post-stack state.