追加操作と出力操作だけの相対順序をどうするか考えます．

次に出力すべき値が \(v\) で，キューに \(v\) が入っていないとき，追加操作を行うべきです．追加操作の前に反転操作が入るかもしれませんが，追加操作と出力操作の相対順序には影響しません．

次に出力すべき値が \(v\) で，キューに \(v\) が入っているとき，すぐに出力操作を行っても解は悪化しません． 次に出力する値が \(v\) であるためには \(v\) がキューの先頭または末尾に置かれている必要があります． キューの先頭にいるなら今すぐ出力して解が悪化しないです． キューの末尾にいる場合，追加操作を行うと解が実行不能になるので，反転操作を行うことになります． すると \(v\) はキューの先頭になり，結局すぐ出力操作をすることになります．

これで，（解が存在するならば）どのような順序で追加操作と出力操作を行うかが分かりました． この \(2N\) 個の操作それぞれについて，その操作の直前までに行った反転操作の回数の偶奇がいくつになるか考えます．

より具体的には，値 \(P_i\) を追加する操作の直前の反転操作の回数の偶奇を \(x_i\)，値 \(P_i\) を出力する操作の直前の反転操作の回数の偶奇を \(y_i\) とします．

\(x_i,y_i\) に課される条件を考えてみます．

まず，\(i<j\), \(P_i<P_j\) かつ，値 \(P_i\) と \(P_j\) が同時にキューに入る瞬間がある，という \((i,j)\) について考えます． \(P_j\) を追加した直後，キュー内での \(P_i,P_j\) の位置関係は，\(P_i\) が先頭に近いです． 反転操作をするたびにこの位置関係は入れ替わります． よって，\(P_j\) の追加操作から \(P_i\) の出力操作までに行う反転操作の回数は偶数であり，\(y_i=x_j\) が従います．

次に，\(i<j\), \(P_i>P_j\) という \((i,j)\) について考えます． これも上のケースと同様に考えることで，\(x_j \neq y_j\) が従います．

今挙げた \(x_i,y_i\) の制約は必要条件ですが，実はこれは十分です． つまり，各出力操作のタイミングで，次に出力したい値の前に別の値が置かれていないことが，上述の \(x_i,y_i\) の条件から従います．

あとは \(x_i,y_i\) を条件を満たすように設定して，隣接する操作間でのスイッチングの回数を最小化すればよいです．

これは一般には難しそうですが，今回の問題では簡単な貪欲法で解けます．

まず，制約によって \(x_i,y_i\) を結べるだけ結び，連結成分に分解します． 一つの連結成分内部で矛盾があったら，実行不可能という答えになります．

すべての連結成分で矛盾がないとします． ここで，これらの連結成分の配置を考えると，森の構造をなしていると分かります．

よって各連結成分の偶奇を試す木DPが可能です． そして実はDPすら必要ありません． 最初の操作が早い順に連結成分を処理していって，直前の操作とのスイッチングを避けるように偶奇を設定すると，それだけで最適解が得られます．

結局，連結成分に分解するところがネックになり，これを segment tree で高速化することで，全体 \(O(N \log N)\) 時間の解法が得られます．

解答例(C++)