Path Split

We need partition the array into the fewest subsequences where adjacent picked values differ by exactly $1$.

The tempting idea is to scan left to right and attach the current value to any existing subsequence ending at $x-1$ or $x+1$. That is not safe. Example: $1,1,3,2,2,4$. If you waste the only tail at $3$ on the first $2$, then the later $4$ is screwed. Optimal tie-breaking is not obvious, so a plain greedy is playing with fire.

Turn paths into matching

Think of each subsequence as a path through positions. If two consecutive elements in a subsequence are positions $i$ and $j$, then we choose a directed link

$i \to j \quad \text{where } i<j \text{ and } |a_i-a_j|=1.$

Each position can have at most one outgoing link and at most one incoming link. If we choose $M$ links total, then those links merge $n$ singleton paths into $n-M$ paths. So minimizing the number of subsequences is the same as maximizing the number of chosen links.

Build a bipartite graph:

• left copy of position $i$ means position $i$ is used as a predecessor,
• right copy of position $j$ means position $j$ gets a predecessor,
• add an edge $i_L \to j_R$ when $i<j$ and $|a_i-a_j|=1$.

A valid set of links is exactly a matching in this graph. Therefore

$\text{answer} = n - \text{maximum matching size}.$

Equivalently, it is the minimum number of unmatched right vertices in a maximum matching.

Use Hall deficiency

For a bipartite graph with right side $R$, the minimum possible number of unmatched right vertices is

$\max_{T \subseteq R} (|T|-|N(T)|).$

So we need compute this maximum without touching the massive edge set.

Here is the key structure. Suppose $T$ contains some later occurrence of value $x$, but skips an earlier occurrence of the same value. Add that earlier occurrence too. Its possible left-neighbors are all earlier adjacent values, and every one of those is also a neighbor of the later occurrence. So adding it increases $|T|$ by $1$ and does not increase $|N(T)|$.

That means an optimal $T$ chooses a prefix of occurrences for every value.

Let $c_x$ be the number of first occurrences of value $x$ chosen into $T$. Let $pos_x[c]$ be the position of the $c$-th occurrence of value $x$, and treat $pos_x[0]$ as before the array.

For a fixed value $y$, which left vertices of value $y$ are in $N(T)$? A position with value $y$ is a neighbor if there is a chosen right vertex after it with value $y-1$ or $y+1$.

So only the latest chosen occurrence among values $y-1$ and $y+1$ matters:

$latest_y = \max(pos_{y-1}[c_{y-1}], pos_{y+1}[c_{y+1}]).$

The number of value-$y$ left vertices added to $N(T)$ is the number of occurrences of $y$ before $latest_y$.

Thus the deficiency is

$\sum_x c_x - \sum_y before_y(\max(pos_{y-1}[c_{y-1}], pos_{y+1}[c_{y+1}])).$

Now the problem is just maximizing this expression.

Parity split

The penalty for value $y$ depends on $c_{y-1}$ and $c_{y+1}$. Those two values have the same parity.

So even variables only interact through odd middle values, and odd variables only interact through even middle values. The total expression splits into two independent DPs. The final answer is:

$bestEven + bestOdd.$

DP over one parity

Take one parity. Its values form a chain:

$..., v, v+2, v+4, ...$

Between two neighboring same-parity values $v$ and $v+2$, the middle value is $y=v+1$.

Suppose the DP currently stores $dp[c]$: the best value so far if we chose $c$ occurrences of value $v$.

Now transition to value $v+2$, choosing $d$ of its occurrences. We gain $d$, because those are added to $|T|$. We pay the middle penalty:

$cost(c,d)=before_y(\max(pos_v[c],pos_{v+2}[d])).$

So:

$newdp[d] = d + \max_c(dp[c]-cost(c,d)).$

Naively this is quadratic between adjacent value buckets. That is where the greedy-ish optimization shows up.

Define:

$A_c = before_y(pos_v[c])$

$B_d = before_y(pos_{v+2}[d])$

Then

$cost(c,d)=\max(A_c,B_d).$

For fixed $d$, let $b=B_d$. Then:

$dp[c]-\max(A_c,b)$

has two cases:

• if $A_c \le b$, it becomes $dp[c]-b$,
• if $A_c > b$, it becomes $dp[c]-A_c$.

The arrays $A_c$ and $B_d$ are nondecreasing because occurrence positions are sorted. So while scanning $d$ from $0$ upward, we maintain:

• prefix maximum of $dp[c]$ for all $A_c \le B_d$,
• suffix maximum of $dp[c]-A_c$ for all $A_c > B_d$.

That gives each transition in linear time in the sizes of the three involved buckets.

We add dummy values outside the real range with count $0$ so boundary penalties are handled naturally. Total complexity is $O(n+\max a_i)$ per test case, which is fine since $a_i \le 2n$ and total $n$ is $10^6$.

No giant matching graph. No sketchy online tie-breaks. Just Hall, parity, DP, and a little sweep. Clean enough to not get murdered by a 2500.