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).