Overview of the solution: enumerate over how many elements are taken from the left, and use some data structure supporting RMQ to update the maximum number of elements takeable from the right incrementally.

---

We rephrase the problem as follows.

There are integer sequences \(X=A\) and \(Y=\text{rev}(A)\). (\(\text{rev}(A)\) is \(A\) reversed.) There is also an empty sequence \(B\).

Repeat the following operation.

• Choose \(X\) or \(Y\), remove its first element, and add it to the beginning or end of \(B\). The chosen sequence must be non-empty.

What is the maximum number of operations?

Choosing \(X\) corresponds to choosing the first element of \(A\), and choosing \(Y\) corresponds to choosing the last element of \(A\).

If at most \(N\) operations can be performed in the rephrased problem, we never use the same element of \(A\) twice, so the answer to the rephrased problem matches the original. Also, since \(B\) must be strictly increasing, performing more than \(N\) operations is impossible.

Thus, the answers to the rephrased problem and the original problem coincide. Below, we consider the rephrased problem.

We define some terminology.

• State \((a,b)\) refers to the state after operating on the first \(a\) elements of \(X\) and the first \(b\) elements of \(Y\).
• State \((a,b)\) is valid if \(B\) can be made strictly increasing when reaching state \((a,b)\).
  • State \((a,b)\) is invalid if it is not valid (this includes cases where the state itself is undefined, e.g., \(a\) or \(b\) exceeds \(N\)).

Once \(B\) ceases to be strictly increasing, no subsequent operation can make it strictly increasing again. Thus, we cannot pass through invalid states, and the sequence \(B\) at any valid state is uniquely determined.

If state \((a,b)\) is valid, then all states \((c,d)\) with \(0\leq c\leq a\) and \(0\leq d\leq b\) are also valid. (Proof sketch: when performing the operations to reach state \((a,b)\), skipping the \((c+1)\)-th and subsequent operations on \(X\) and the \((d+1)\)-th and subsequent operations on \(Y\) still leaves \(B\) strictly increasing.)

First, find the maximum \(x\) such that state \((0,x)\) is valid, and call this \(p\) (this is easy). The rephrased problem can be solved if we can solve the following subproblem.

Suppose state \((a,b)\) is valid, and state \((a,b+1)\) is invalid. Find the maximum \(c\) such that state \((a+1,c)\) is valid.

Intuitively, we will decrease \(b\) by some amount, increase \(a\), and then increase \(b\) as much as possible.

Since state \((a,b)\) is valid, all states \((a,x)\) with \(0\leq x\leq b\) are valid.

Find the maximum \(x\) such that we can move from state \((a,x)\) to state \((a+1,x)\); call it \(s\). This can be processed using some data structure supporting RMQ. Then, move to state \((a+1,s)\) and increase \(s\) as much as possible to obtain \(c\). (Moving from some state other than \((a,s)\) to \((a+1,*)\) would either pass through \((a+1,s)\) or stop earlier, so it is never beneficial.)

If we can efficiently solve this “increase as much as possible” part, we can solve the problem.

First, whether we can go from state \((a+1,0)\) to \((a+1,1)\) can be determined immediately. If not, the increase stops there. Below, we consider the problem of increasing \(x\) as much as possible from state \((a+1,x)\) with \(1\leq x\).

Clearly, we need \(x\leq p\). We do binary search to determine how far we can increase.

To determine whether reaching state \((a+1,t)\) is possible, consider: since state \((0,p)\) is valid, \(1\leq x\), and \(t\leq p\), the condition for being able to move from state \((a+1,x)\) to state \((a+1,t)\) can be rephrased as:

• Let \(mi\) and \(ma\) be the minimum and maximum values of \(B\) at state \((a+1,x)\). There is no element in \(Y\) from the \((x+1)\)-th to the \(t\)-th that is between \(mi\) and \(ma\) (inclusive).

This can be determined using a Wavelet Matrix, or alternatively, since \(1\leq x\) implies \(mi\leq Y_1\leq ma\), by splitting based on comparison with \(Y_1\) and using RMQ.

The time complexity is \(O(N\log^2 N)\) or \(O(N\log N)\), which is sufficiently fast.