Let us first decide the relative order of the append and output operations alone.

If the next value to output is \(v\) and \(v\) is not in the queue, we should perform an append operation. A reverse operation may come before the append operation, but it does not affect the relative order of the append and output operations.

If the next value to output is \(v\) and \(v\) is in the queue, performing the output operation immediately does not worsen the solution. For \(v\) to be the next value output, \(v\) must be at the front or the back of the queue. If it is at the front, outputting it right away does not worsen the solution. If it is at the back, performing an append operation would make the solution infeasible, so we must perform a reverse operation. Then \(v\) moves to the front of the queue, and we end up performing the output operation immediately after all.

We now know in what order to perform the append and output operations (if a solution exists). For each of these \(2N\) operations, consider the parity of the number of reverse operations performed before it.

More specifically, let \(x_i\) be the parity of the number of reverse operations performed before the operation appending the value \(P_i\), and let \(y_i\) be the parity of the number of reverse operations performed before the operation outputting the value \(P_i\).

Let us consider the conditions imposed on \(x_i,y_i\).

First, consider a pair \((i,j)\) such that \(i<j\), \(P_i<P_j\), and the values \(P_i\) and \(P_j\) are simultaneously in the queue at some moment. Immediately after \(P_j\) is appended, \(P_i\) is closer to the front of the queue than \(P_j\). Each reverse operation flips this relative order. Thus, the number of reverse operations performed between the append operation of \(P_j\) and the output operation of \(P_i\) is even, which implies \(y_i=x_j\).

Next, consider a pair \((i,j)\) such that \(i<j\) and \(P_i>P_j\). A similar argument to the above case implies \(x_j \neq y_j\).

The constraints on \(x_i,y_i\) above are necessary, and in fact they are also sufficient. That is, these conditions on \(x_i,y_i\) imply that, at the time of each output operation, no other value is in front of the value to be output next.

All that remains is to assign \(x_i,y_i\) so that the conditions are satisfied and the number of switches between adjacent operations is minimized.

This seems difficult in general, but in this problem, a simple greedy algorithm works.

First, connect the variables \(x_i,y_i\) wherever a constraint relates them, and decompose them into connected components. If a connected component contains a contradiction, the task is infeasible and the answer is -1.

Suppose that no connected component has a contradiction. Looking at how these connected components are arranged, we find that they form a forest structure.

Thus, a tree DP that tries each parity for each connected component is possible. In fact, even the DP is unnecessary. Processing the connected components in ascending order of their earliest operations and setting each parity to avoid a switch with the immediately preceding operation yields an optimal solution.

The bottleneck turns out to be the decomposition into connected components, and speeding this up with a segment tree gives a solution in \(O(N \log N)\) time overall.

Sample solution (C++)