Let **Page[i]** be the number of the page printed at the position
**i** and **Pos[i]** the position of page number **i** (also
**Pos[Page[i]]=i** and **Page[Pos[i]]=i**). Let **Left[i]** and
**Right[i]** be the left and right neighbors of page number **i**
(also **Left[i]=Page[Pos[i]-1]**, **Right[i]=Page[Pos[i]+1]**).

How does the folded paper look like (in case it is possible to fold it)?
On the top there is the page number **1**, under the page number **1**
is the page number **2**, ... and at the bottom is the page number **N**.
Each page **i** is connected with the pages **Left[i]** and **Right[i]**.
If the printed side of some page **i** is facing up then the connection
to **Left[i]** is on the left side and connection to **Right[i]** is on the
right side of the resulting column of pages. Moreover, the printed sides of the
pages **Left[i]** and **Right[i]** are facing down. If the printed
side of the page **i** is facing down, the whole situation is reversed.

The rules stated above determine exactly how should the resulting column of pages look like. E.g. consider the example input from the problem statement. There were 5 pages, printed in the order 3-1-5-4-2. Suppose the printed side of the page number 1 is facing up. From this we may deduce that 1 and 3 have to be connected on the left side, 1 and 5 on the right side, 5 and 4 on the left side and pages 4 and 2 have to be connected on the right side. Clearly it is possible to fold the paper this way if and only if no two connections intersect each other. But how to check this?

Imagine a horizontal sweeping plane moving from the top to the bottom of
our column of paper. At each moment the sweeping plane intersects some of
the connections, some of them are completely above and some are below
the sweeping plane. We will call the intersected connections **open**
and all other connections **closed**. Suppose that the sweeping plane
is between pages **i-1** and **i**. What happens when it moves
below the page **i**? If the page **i** is connected to some page **j**
such that **i<j**, a connection from **i** to **j** is opened.
If **i>j**, the connection from **j** to **i** is closed.
Clearly the connections don't intersect if and only if for each two
connections **c** and **d** on the same side (e.g. left or right)
the following condition holds: If **c** is opened before **d**
then **c** is closed after **d**.

This idea leads to the following algorithm: Suppose that the pages printed at odd
positions are facing up. (The other case is symmetric with this one.)
We will use two stacks, one for the left side and one for the right one.
In these stacks we will store the currently open connections. The most recently
opened connection will be at the top of the stack.
At the beginning both stacks are empty.
We will iterate through all **i** from **1** to **N**,
in the **i**-th iteration the sweeping plane will pass over the
page number **i**: We check all (at most two) connections involving
page number **i**. (Note that these connections are determined by the values
**Pos**, **Page**, **Left** and **Right** defined above.)
If a connection is opened, we push it onto the corresponding stack.
If a connection is closed, we check whether it is on the top of the
corresponding stack. If yes, we pop it from the stack. Otherwise
the algorithm terminates and the answer is "NO".
If we finish all the iterations without finding two intersecting
connections the answer is "YES".
Both time and space complexity of this algorithm are **O(N)**.