Against the Difference

The whole problem is about realizing that blocks are extremely rigid. A block cannot be “some equal values”; if the value is $x$, the block must contain exactly $x$ copies of $x$. So every block has the form:

$[x,x,\dots,x] \quad \text{with length } x.$

We need the longest subsequence that can be split into such blocks.

DP State

Let $dp[i]$ be the maximum length of a neat subsequence using only the prefix $a_1, a_2, \dots, a_i$.

There is always the boring option: ignore $a_i$.

$dp[i] \ge dp[i-1]$

Now suppose we actually use $a_i$. Let $a_i=x$. If $a_i$ is the final element of the last block, then the last block must be exactly $x$ selected occurrences of value $x$.

So the question becomes: do we have $x$ occurrences of value $x$ ending at position $i$?

Tracking Occurrences

For every value $x$, store all positions where $x$ appeared so far.

When we are at position $i$ with value $x$, append $i$ to pos[x]. Let $m$ be the number of occurrences of $x$ seen so far.

If $m < x$, then we cannot form a block of value $x$ ending here. Not enough copies. Brutal, but fair.

If $m \ge x$, then we can use the last $x$ occurrences of $x$ as one block.

Let their first position be $p$. In zero-indexed occurrence-list terms, that is:

$p = pos[x][m-x]$

Then everything before this block must come from positions before $p$, so the previous best value is $dp[p-1]$. Adding this new block gives:

$dp[i] = \max(dp[i], dp[p-1] + x)$

Why The Last $x$ Occurrences Are Best

This is the key little trick.

Imagine a block of value $x$ ending at the current position. Its first selected occurrence must be early enough so that there are at least $x$ occurrences of $x$ from there through the current position.

Among all valid starts, we want the latest possible start, because then the prefix before the block is as large as possible. Since $dp$ over prefixes never decreases, a later start can only help or tie.

The latest possible start is exactly the first of the last $x$ occurrences of $x$.

So we never need to try all previous occurrences. No nested loop, no drama, no accidental $O(n^2)$ faceplant.

Algorithm

For each test case:

1. Initialize $dp[0]=0$.
2. Keep pos[value], the positions where each value appeared.
3. For each index $i$ from $1$ to $n$:
   • Read $x=a_i$.
   • Set $dp[i]=dp[i-1]$.
   • Append $i$ to pos[x].
   • If pos[x].size() >= x, let $p$ be the first position among the last $x$ occurrences of $x$.
   • Update $dp[i]=\max(dp[i], dp[p-1]+x)$.
4. Output $dp[n]$.

Correctness Proof

We prove that $dp[i]$ is the best possible neat subsequence length inside the first $i$ elements.

Base case: $dp[0]=0$, and the empty array is neat, so this is correct.

For the transition, take an optimal neat subsequence inside the first $i$ elements.

If it does not use $a_i$, then it lies entirely in the first $i-1$ elements, so its length is at most $dp[i-1]$, which our transition considers.

Otherwise, consider the last block of this subsequence. Since it ends at $a_i=x$, that block must contain exactly $x$ selected occurrences of value $x$. Therefore, at least $x$ occurrences of $x$ must have appeared up to position $i$.

Let $p$ be the first position among the last $x$ occurrences of $x$ up to $i$. Any valid block ending at $i$ must start no later than $p$, because after $p$ there are fewer than $x$ occurrences of $x$. Since prefix DP is nondecreasing, choosing the block to start at $p$ gives a previous prefix value at least as good as any earlier valid start. Thus the best block ending at $i$ contributes exactly $dp[p-1]+x$, which our transition considers.

So every optimal solution is covered by either skipping $a_i$ or ending a block at $i$. Therefore $dp[i]$ is correct.

By induction, $dp[n]$ is the length of the longest neat subsequence.

Complexity

Each position is appended once and processed once.

Time complexity: $O(n)$ per test case.

Memory complexity: $O(n)$ per test case.