Longest Good Subsequence

The permutation is bait. Useful bait, but still bait. The real job is to understand which arrays $b$ are good without ever constructing $p$ during the DP.

Characterizing good arrays

Fix a candidate array $b$ of length $m$. Suppose $b_i=x$. From the definition:

• $p_i$ is the minimum on $[x,i]$, so $p_i < p_k$ for every $x <= k < i$.
• If $x>1$, then $x$ is the smallest valid left endpoint, so after extending one step left, $p_i$ must stop being the minimum. Since $p_i$ is already smaller than everything in $[x,i]$, this means $p_{x-1} < p_i$.

Now assume $x<i$. Then $b_x$ must equal $x$. If $b_x<x$, the rule for position $x$ would force $p_x < p_{x-1}$. But from position $i$, we also have $p_i < p_x$ and $p_{x-1}<p_i$. That gives $p_x < p_{x-1} < p_i < p_x$, which is nonsense.

Also, every value in positions $x..i$ must be at least $x$. If some $k$ with $x <= k < i$ had $b_k < x$, then the interval for position $k$ includes $x-1$, so $p_k < p_{x-1}$. But position $i$ says $p_i < p_k$, and again $p_{x-1}<p_i$. Contradiction.

So we get the necessary condition:

For every $i$ with $b_i=x$, either $x=i$, or $b_x=x$ and $min(b_x,b_{x+1},...,b_i) >= x$.

This condition is also sufficient. Assign permutation values by sorting indices by the pair $(b_i,-i)$, smaller pair gets smaller $p$. For $b_i=x$, every $k$ in $[x,i-1]$ has $b_k>=x$; if $b_k=x$, then $k<i$ makes $(b_i,-i)$ smaller than $(b_k,-k)$. Thus $p_i<p_k$ for all $k$ in $[x,i-1]$. Also, if $x>1$, then $b_{x-1}<=x-1<x$, so $p_{x-1}<p_i$. That exactly matches the required smallest left endpoint.

So the characterization is done.

Blocks

The condition says this:

If a value $x$ appears at subsequence position $x$, it may appear again later. But between that first $x$ and any later $x$, all chosen values must be at least $x$.

So each value creates a block. Larger values can form nested blocks inside it. Smaller values cannot appear inside it. That is the whole problem hiding under a trench coat.

One more important detail: to place value $x$ as the first element of an $x$-block, the current good sequence must already have length at least $x-1$. If it has more, we can take a prefix of length $x-1$, because every prefix of a good sequence is good.

DP state

Let $D(l,r)$ be meaningful when $a_l=a_r=x$.

$D(l,r)$ is the maximum total length of a good sequence after completing an $x$-block that starts at original position $l$ and ends at original position $r$, assuming we already had a good prefix of length $x-1$ before taking $a_l$.

This is why $D(l,l)=x$, not $1$. We are counting the total length after placing value $x$ at subsequence position $x$.

We compute $D(l,*)$ for $l$ from right to left, so any nested block starting later has already been computed.

Computing one row

Fix $l$, and let $x=a_l$. Maintain cur, the best total length of an open $x$-block after scanning some prefix to the right of $l$.

Initially, cur = x.

Now scan $r=l+1..n$:

• If $a_r < x$, we cannot use it inside this $x$-block. Skip it.
• If $a_r = x$, we can append another $x$ to the same block. Do cur++, and set $D(l,r)=cur$.
• If $a_r = v > x`, then it can only help by forming a nested$v$-block. Such a block may start at an occurrence$s$of value$v$only when, before$s$, we can already make length at least$v-1$. Store the earliest such$s$ as first[v].

When we are at position $r$ with value $v$ and first[v] exists, the nested block from first[v] to $r$ is usable, so:

$cur = max(cur, D(first[v], r))$.

Why is earliest start enough? Same required prefix length, more available elements between start and end. A later start cannot magically be better. CP problems love pretending this is subtle; it really is just monotonicity doing its job.

Top level

The final answer is the same process without an outer block. Start with ans=0. While scanning positions from left to right, value $v$ can start its first block once ans >= v-1. Keep earliest feasible first[v]; whenever another $v$ appears, update:

$ans = max(ans, D(first[v], r))$.

This also naturally handles the empty answer. For example, an array of all $2$s gives $0$, because there is no way to create the required first position before placing a $2$.

Complexity

For every left endpoint we do one linear scan, so the time is $O(n^2)$ per test case. The DP has $n(n+1)/2$ useful entries. Since the answer is at most $15000$, each entry fits in int16_t, giving $O(n^2)$ memory with a comfortable constant.