Let \(x\) be the minimum \(i\) that violates the condition.

Consider the case \(x \equiv 1 \mod 2\).

Now, we have \(P_x>P_{x+1}\). Let us look at the magnitude relation between \(P_x\) and \(P_{x+2}\), and do the following.

• If \(P_x>P_{x+2}\) (or \(x=2N-1\)): swap \(P_x\) and \(P_{x+1}\).
• If \(P_x<P_{x+2}\): swap \(P_{x+1}\) and \(P_{x+2}\).

After this, the conditions for \(i=x,x+1\) will be satisfied. Also, since \(P_{x-1}>P_x>P_{x+1}\), the condition for \(i=x-1\) will remain satisfied.

The case \(x \equiv 0 \mod 2\) can be handled similarly.

Then, in each operation, the value of the minimum \(i\) violating the condition increases by at least \(2\), so the whole \(P\) will satisfy the conditions after at most \(N\) operations.

Implementing the above procedures solves the problem in \(O(N)\) time.

Sample code (c++)