数列は 0-indexed とする．

一番最初に \(A[0]\) を取り出すと決め打ったとき，先頭 \(L(\geq 1)\) 項と末尾 \(R(\geq 0)\) 項を使えるか？という判定問題は，以下が必要十分である．

1. \(A[0:L) + A[N-R:N)\) に重複がない

2. \(A[0:L)\) は左から見て毎回 min または max を更新する

3. \((A[0])+reverse(A[N-R:N))\) は左から見て毎回 min または max を更新する

4. 任意の \(0 \leq i < L-1, N-R \leq j < N-1\) について、次を満たす：

   • \(A[i] < A[j] < A[i+1] < A[j+1]\) が 成りたたない
   • \(A[j+1] < A[i+1] < A[j] < A[i]\) が 成りたたない

\(L\) を決め打ったときの最大の \(R\) を毎回求める．\(R\) は単調性があるので尺取りで求めることができる．\(1\) つ目については，\(xy\) 平面上に点 \((A[j],A[j+1]) (N-R \leq j < N-1)\) がプロットしてあるとき，領域 \(A[L]<x<A[L+1]\) の領域にある点の \(y\) 座標の最大値は \(A[j+1]\) 未満か？ と言い換えることができる．条件を満たさない場合は点 \((A[N-R],A[N-R+1])\) を削除して \(R\) をインクリメントして再度判定すればよい．\(2\) つ目も同様にできる．これらは segtree と min/max を取得できる multiset を使えば \(O(N\log N)\) で解ける．

必要性

1, 2, 3 は問題の設定から容易にわかる．4 については，\(A[i+1]\) と \(A[j]\) のどちらかが \(4\) つの中で最後に \(B\) に追加されるが，もし成り立たないと仮定すると min と max の両方とも更新しないことから従う．

十分性

操作を行う順序を有向辺で表現する．まず，先頭側では \(A[0]\to A[1]\to \cdots A[L-1]\) であり，同様に末尾側では \(A[0]\to A[N-1]\to \cdots A[N-R]\) である．さらに，（\(A[0]<A[i]<A[j]\) または \(A[0]>A[i]>A[j]\)） かつ \(i,j\) が先頭側と末尾側で異なる場合に \(A[i]\to A[j]\) とする．これが DAG になっていることを示せばよい．

仮に閉路が存在すると仮定する．先頭側だけ、または末尾側だけでは，条件 2, 3 により毎回 min/max を更新するので矛盾は起きない．したがって，閉路は必ず先頭側と末尾側をまたぐ．

先頭側を \(P[0]=A[0], P[1]=A[1],\cdots,P[L-1]=A[L-1]\)，末尾側を \(Q[0]=A[0],Q[1]=A[N-1],\cdots,A[R]=A[N-R]\) と書くことにする．単純閉路を一つとり，\(P[a_1]\to \cdots \to P[b_1]\to Q[c_1]\to \cdots \to Q[d_1]\to P[a_2]\to \cdots \to P[b_2]\to Q[c_2]\to \cdots \to Q[d_2]\to\ldots\) とする．

もしこの閉路が先頭側と末尾側を \(2\) 回より多く行き来しているとする．このとき，ある \(t\) が存在して \(a_{t+1}\geq b_t\) が成り立つ（もし成り立たなければ \(a_2<a_1,a_3<a_2,\ldots,a_1<a_m\) となり矛盾）．すると \(P[a_{t}]\to \cdots \to P[b_t]\to Q[c_t]\to \cdots \to Q[d_t]\to P[a_{t+1}]\to \cdots P[b_{t+1}]\) は単に \(P[a_t]\to \cdots \to P[b_{t+1}]\) に置き換えられる．この縮約を繰り返すと，先頭側と末尾側をちょうど \(2\) 回行き来するような閉路を取ることができる．これを \(P[a]\to \cdots \to P[b]\to Q[c]\to \cdots Q[d]\to P[a]\) とする．

このとき，\(P[b]\) と \(Q[c]\) はともに \(A[0]\) より大きいか小さいかのどちらかである．\(Q[d]\) と \(P[a]\) も同様である．もし仮に \(4\) つが全て \(A[0]\) より大きいと仮定すると \(P[a]<P[b]<Q[c]<Q[d]<P[a]\) となり矛盾．すべて \(A[0]\) より小さい場合も同様．したがって，\(Q[c]<P[b]<A[0]<Q[d]<P[a]\) または \(Q[c]>P[b]>A[0]>Q[d]>P[a]\) のいずれかである．

\(Q[c]<P[b]<A[0]<Q[d]<P[a]\) の場合を考える．\(P[a]>A[0]>P[b]\) であることより，ある \(i\) が存在して \(P[i]>A[0]>P[i+1]\) である．また，\(Q[c]<A[0]<Q[d]\) であることより，ある \(j\) が存在して \(Q[j]<A[0]<Q[j+1]\) である．このとき，\(P[i]\geq P[a],P[i+1]\geq P[b], Q[j]\leq Q[c],Q[j+1]\leq Q[d]\) である．これらの不等式をまとめると \(P[j]\lt P[i+1]\lt Q[j+1]\lt P[i]\) となるが，条件 \(4\) の \(2\) つ目に違反する．\(P[c]>Q[b]>A[0]>Q[d]>P[a]\) も同様である．

よって，閉路が存在するという仮定が誤りであり，十分性は示された．