Railroad Siding

A railroad siding consists of two dead‐end sidetracks, labeled 1 and 2. The siding is entered by track A and left by track B. There are \(n\) cars on track A, numbered from \(1\) to \(n\). They arrive in increasing order (i.e. 1, 2, \(\dots\), n). The cars are to be transferred via one of the two sidetracks so that they exit via track B in a given order (a permutation of \(1,2,\dots,n\)).

Each car is transferred exactly once from track A to one of the sidetracks, and later (possibly after some transfers of the remaining cars) once from that sidetrack to track B. The sidetracks can hold arbitrarily many cars. However, each sidetrack works as a stack (last-in, first-out), so cars can only leave in the reverse order in which they were placed on that sidetrack.

Determine whether a given permutation is achievable using the two sidetracks under these rules.

Note: When placing a car onto a sidetrack, it is only allowed if the car is smaller than the car currently at the top of that sidetrack (if it is non-empty). This ensures that the sidetrack maintains a monotonically decreasing order from top to bottom.

For example, if \(n = 4\) and the desired departure order is \(4\ 1\ 3\ 2\), then it is impossible to achieve the order.

inputFormat

The first line contains a single integer \(n\) (number of cars). The second line contains \(n\) integers representing the desired permutation (departure order) separated by spaces.

outputFormat

Output a single line: YES if it is possible to achieve the desired departure order using the two sidetracks, or NO otherwise.

sample

5
1 2 3 4 5

YES