解法の概略：左何項使うかを全探索し、RMQを行える何らかのものを使うと右何項使えるかを差分更新できます。

---

問題を以下のように言い換えます。

整数列 \(X=A,Y=\text{rev}(A)\) がある。（\(\text{rev}(A)\) は \(A\) を前後反転した数列）また、空の数列 \(B\) がある。

以下の操作を繰り返す。

• \(X\) または \(Y\) を選び、その先頭の要素を削除し、\(B\) の先頭または末尾に追加する。ただし選んだ数列が空であってはならない。

操作を最大で何回行えるか？

\(X\) を選ぶことは \(A\) の先頭を選ぶことに、\(Y\) を選ぶことは \(A\) の末尾を選ぶことに対応します。

言い換え後の問題で \(N\) 回以下しか操作できない場合、\(A\) の同じ要素を使っていることはなく、言い換え後の問題の答えが元の問題の答えと一致します。また、\(B\) が狭義単調増加している必要があることより、\(N\) 回より多く操作することはできません。

そのため、言い換え後の問題と元の問題の答えは一致します。以降、言い換え後の問題を考えます。

用語を定義します。

• 状態 \((a,b)\) を、\(X\) の先頭 \(a\) 要素と \(Y\) の先頭 \(b\) 要素に操作した状態とします。
• 状態 \((a,b)\) が valid であるとは、状態 \((a,b)\) に辿り着いたときに \(B\) を狭義単調増加にできることとします。
  • 状態 \((a,b)\) が invalid であるとは、状態 \((a,b)\) が valid でないこととします（\(a,b\) が \(N+1\) 以上であるなどして状態自体が無効である場合も含みます）。

\(B\) がひとたび狭義単調増加でなくなったら、その後の操作で狭義単調増加になることはありません。そのためinvalidな状態を経由することはできず、またvalidな状態での \(B\) は一意に定まります。

状態 \((a,b)\) がvalidであるとき、状態 \((c,d)\) \((0\leq c\leq a,0\leq d\leq b)\) はすべてvalidです。（証明の概略：状態 \((a,b)\) に辿り着く操作を行うときに、\(X\) の \(c+1\) 回目以降と \(Y\) の \(d+1\) 回以降の操作をスキップしても依然として \(B\) は狭義単調増加です。）

はじめ、状態 \((0,x)\) がvalidであるような \(x\) の最大値を求め、この \(x\) を \(p\) とします（これは容易です）。以下の問題が解ければ、言い換え後の問題が解けます。

状態 \((a,b)\) がvalidであり、さらに状態 \((a,b+1)\) はvalidでないような \(a,b\) がある。 状態 \((a+1,c)\) がvalidであるような \(c\) の最大値を求めよ。

直感的には、\(b\) をある程度減らす→ \(a\) を増やす→ \(b\) を増やせるだけ増やす、ということをします。

状態 \((a,b)\) がvalidであることから、状態 \((a,x)\) \((0\leq x\leq b)\) はすべてvalidです。

状態 \((a,x)\) から状態 \((a+1,x)\) に移動できるような \(x\) の最大値を求め、これを \(s\) とします。これはRMQをできる何らかのデータ構造を使って処理できます。その後状態 \((a+1,s)\) に移動し、そこから \(s\) を増やせるだけ増やすことで \(c\) を求めます（\(s\) でないところから状態 \((a+1,*)\) に移動しても、そこから状態 \((a+1,s)\) を経由することになるかその前に増やせなくなるので得しません）。

この増やせるだけ増やすパートを高速に解くことができれば、この問題を解くことができます。

まず、状態 \((a+1,0)\) から \((a+1,1)\) にできるかはすぐに判定できます。できなかったらその時点で増やす操作は終わりです。以降、状態 \((a+1,x)\) \((1\leq x)\) から \(x\) をできるだけ増やす問題を考えます。

明らかに、\(x\leq p\) でなければなりません。二分探索して、どこまで増やせるか判定します。

状態 \((a+1,t)\) にすることが可能であるか判定することを考えます。状態 \((0,p)\) がvalidであること、\(1\leq x\) であること、\(t\leq p\) であることより、状態 \((a+1,x)\) から状態 \((a+1,t)\) に移動できる条件は以下のように言い換えられます。

• 状態 \((a+1,x)\) での \(B\) の最小値を \(mi\)、最大値を \(ma\) とする。\(Y\) の \(x+1\) 項目から \(t\) 項目に \(mi\) 以上 \(ma\) 以下の要素が存在しない。

これの判定は Wavelet Matrix で行うことができるほか、\(1\leq x\) より \(mi\leq Y_1\leq ma\) なので、\(Y_1\) との大小で分けてRMQをすることでも判定できます。

計算量は \(O(N\log^2 N)\) または \(O(N\log N)\) で、十分高速です。