Distinct Elements

Let $last_i(x)$ be the last position where value $x$ appears inside the prefix $a[1..i]$. If $x$ has not appeared yet, ignore it.

The important question is: for fixed ending position $i$, how much does one value $x$ contribute to

$b_i=f(a[1,i])+f(a[2,i])+\cdots+f(a[i,i])?$

Suppose the last occurrence of $x$ up to position $i$ is $p$. Then $x$ appears in subarray $a[l..i]$ exactly when $l \le p$. There are exactly $p$ such starts: $1,2,\ldots,p$.

So value $x$ contributes $p$ to $b_i$. Summing over all distinct values seen so far gives:

$b_i=\sum_x last_i(x).$

That is the key observation. The scary definition with a pile of subarrays collapses into a very chill sum of last positions.

What changes when we append position $i$?

Let

$d_i=b_i-b_{i-1}.$

Only the value $a_i$ can change the sum of last positions.

There are two cases:

1. $a_i$ is a brand-new value.

   Then it did not contribute before, and now its last position is $i$. So:

   $d_i=i.$

2. $a_i$ already appeared before.

   Say its previous last occurrence was $p$. In the sum, this value used to contribute $p$, and now it contributes $i$. So:

   $d_i=i-p.$

   Therefore:

   $p=i-d_i.$

This means $d_i$ tells us exactly what kind of move to make.

Construction

Process positions from left to right. Maintain owner[p], the value whose current last occurrence is position $p$. Only current last positions matter.

For each position $i$:

• Compute $d_i=b_i-b_{i-1}$.
• If $d_i=i$, create a new value and put it at $a_i$.
• Otherwise, the previous last occurrence must be $p=i-d_i$. Take the value stored at owner[p], put it at $a_i$, and move its last occurrence from $p$ to $i$.

Because the statement guarantees that some answer exists, whenever we need owner[p], it will exist. No need for detective work, no need for backtracking, no cursed DP.

We use new labels $1,2,3,\ldots$ as needed. At most $n$ labels are created, so every $a_i$ stays between $1$ and $n$.

Why this is correct

We maintain the invariant that after processing position $i$, owner[p] correctly records which value has current last occurrence $p$, and the constructed prefix produces the given $b_i$.

Initially, nothing exists and the sum is $0$.

At step $i$:

• If $d_i=i$, adding a new value increases the sum of last positions by exactly $i$.
• Otherwise, choosing the value whose last occurrence is $p=i-d_i$ moves its contribution from $p$ to $i$, increasing the sum by $i-p=d_i$.

So after the step, the sum becomes $b_{i-1}+d_i=b_i$. The invariant continues to hold.

Thus the final array produces exactly the given $b$.

Complexity

Each position is processed once, with $O(1)$ work. Total complexity is $O(n)$ per test case, and memory usage is $O(n)$.