Train Carriage Scheduling

Problem Background

Special for beginners, ^_^

Problem Description

There is a train station with tracks as shown in the figure. Each train enters from direction A and leaves from direction B, and its carriages can be recombined. Suppose a train coming from direction A has $n$ carriages ($n\le 1000$), numbered in order $1,2,3,\dots,n$. Assume that before entering the station, the carriages are not connected to each other, and they can move by themselves onto the track at direction B. Also assume that station C can hold any number of carriages. But 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 know whether it is possible to make it leave from direction B in the order $a_1,a_2,\dots,a_n$. Please determine whether the specified carriage order can be obtained.

Input Format

The first line is an integer $n$ ($n\le 1000$), the number of carriages. The second line contains $n$ numbers, the specified carriage order.

Output Format

If the specified carriage order can be obtained, output the string YES; otherwise output NO (note: uppercase, without quotes). These words must be printed exactly as shown (do not translate).

Sample Input 1

5
5 4 3 2 1

Sample Output 1

YES

Hint

Analysis: The whole scheduling process is actually simulating a push/pop (stack) process. We can divide it into three states: before-stack, in-stack, after-stack. We observe that when a number is popped, the numbers smaller than it must either have already been popped or still be in the stack (cannot be in the before-stack state), and the numbers in the stack are in descending order (viewed from top to bottom of the stack). For example, if $5$ is popped, then $1,2,3,4$ must have either already been popped before $5$, or still be in the stack (if $1,3,4$ are in the stack, from top to bottom they are $4,3,1$); they cannot be in the before-stack state. If a number is to be popped, then all numbers currently in the stack must be smaller than it, otherwise it contradicts the property of the stack and is invalid. So we can solve it as follows:

Scan from the first number; $a[i]$ is the number currently being popped. If there is 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 after-stack, and then the numbers in $[1, a[i]-1]$ that have not yet been popped are marked as in-stack. We can use $0$ for undetermined, $1$ for in-stack, $2$ for after-stack.

Constraints

Time limit 1s, memory limit 1024KiB for each test case.