Sequences are \(0\)-indexed.

Consider the decision problem: if we fix that the first element taken is \(A[0]\), can we use the first \(L\,(\geq 1)\) elements and the last \(R\,(\geq 0)\) elements? We can do so if and only if:

1. \(A[0:L) + A[N-R:N)\) contains no duplicates.

2. \(A[0:L)\), viewed left to right, updates the minimum or maximum at every step.

3. \((A[0])+\text{reverse}(A[N-R:N))\), viewed left to right, updates the minimum or maximum at every step.

4. For all \(0 \leq i < L-1\) and \(N-R \leq j < N-1\), the following hold:

   • \(A[i] < A[j] < A[i+1] < A[j+1]\) does not hold.
   • \(A[j+1] < A[i+1] < A[j] < A[i]\) does not hold.

For each fixed \(L\), we find the maximum \(R\). Since \(R\) is monotone, it can be found using a two-pointer approach. For condition 1: when points \((A[j],A[j+1])\ (N-R \leq j < N-1)\) are plotted on the \(xy\)-plane, we can rephrase it as: is the maximum \(y\)-coordinate among points in the region \(A[L]<x<A[L+1]\) less than \(A[j+1]\)? If the condition is violated, remove the point \((A[N-R],A[N-R+1])\), increment \(R\), and check again. Condition 2 can be handled similarly. These can be solved in \(O(N\log N)\) using a segment tree and a multiset supporting min/max queries.

Necessity

Conditions 1, 2, 3 follow easily from the problem setting. For condition 4, note that either \(A[i+1]\) or \(A[j]\) is the last of the four to be added to \(B\); assuming the condition fails implies that it updates neither the minimum nor the maximum, yielding a contradiction.

Sufficiency

We represent the order of operations using directed edges. On the front side, \(A[0]\to A[1]\to \cdots \to A[L-1]\), and similarly on the back side, \(A[0]\to A[N-1]\to \cdots \to A[N-R]\). Furthermore, if (\(A[0]<A[i]<A[j]\) or \(A[0]>A[i]>A[j]\)) and \(i\) and \(j\) are on different sides (front and back), we add \(A[i]\to A[j]\). It suffices to show that this is a DAG.

Suppose for contradiction that a cycle exists. A cycle within only the front side or only the back side would contradict conditions 2 and 3, since each step updates a min/max. Thus, any cycle must cross between the front and back sides.

Let the front side be \(P[0]=A[0], P[1]=A[1],\ldots,P[L-1]=A[L-1]\) and the back side be \(Q[0]=A[0],Q[1]=A[N-1],\ldots,Q[R]=A[N-R]\). Take a simple cycle: \(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\).

Suppose this cycle crosses between the front and back sides more than twice. Then there exists some \(t\) such that \(a_{t+1}\geq b_t\) (otherwise \(a_2<a_1, a_3<a_2,\ldots, a_1<a_m\), a contradiction). Then \(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 \to P[b_{t+1}]\) can simply be replaced by \(P[a_t]\to \cdots \to P[b_{t+1}]\). Repeating this contraction, we can obtain a cycle that crosses between the front and back sides exactly twice. Write it as \(P[a]\to \cdots \to P[b]\to Q[c]\to \cdots \to Q[d]\to P[a]\).

At this point, \(P[b]\) and \(Q[c]\) are both greater than \(A[0]\) or both less than \(A[0]\), and similarly for \(Q[d]\) and \(P[a]\). If we assume all four are greater than \(A[0]\), we get \(P[a]<P[b]<Q[c]<Q[d]<P[a]\), a contradiction. The case where all are less than \(A[0]\) is analogous. Thus, either \(Q[c]<P[b]<A[0]<Q[d]<P[a]\) or \(Q[c]>P[b]>A[0]>Q[d]>P[a]\).

Consider the case \(Q[c]<P[b]<A[0]<Q[d]<P[a]\). Since \(P[a]>A[0]>P[b]\), there exists some \(i\) such that \(P[i]>A[0]>P[i+1]\). Since \(Q[c]<A[0]<Q[d]\), there exists some \(j\) such that \(Q[j]<A[0]<Q[j+1]\). Then \(P[i]\geq P[a]\), \(P[i+1]\leq P[b]\), \(Q[j]\leq Q[c]\), \(Q[j+1]\geq Q[d]\). Combining these inequalities gives \(Q[j]<P[i+1]<Q[j+1]<P[i]\), which violates the second part of condition 4. The case \(Q[c]>P[b]>A[0]>Q[d]>P[a]\) is analogous.

Thus, the assumption that a cycle exists is false, and sufficiency is proved.