Replace with Occurrences

We need build an array $a$ such that for every position $i$, the number of times $a_i$ appears in the whole array equals $b_i$.

The key is to stop thinking about values one position at a time. Values in $a$ create groups.

If some value $x$ appears in positions:

$$p_1, p_2, \dots, p_k$$

then $f(x)=k$, so every one of those positions must satisfy:

$$b_{p_1}=b_{p_2}=\dots=b_{p_k}=k$$

So a value that appears $k$ times can only be assigned to positions whose $b_i$ is exactly $k$.

That gives the whole problem away.

Necessary condition

For each possible value $k$, count how many positions want occurrence count $k$:

$$c_k = |\{i : b_i = k\}|$$

Those $c_k$ positions must be split into groups of size exactly $k$.

So we need:

$$c_k \equiv 0 \pmod{k}$$

for every $k$.

If this fails for even one $k$, the answer is impossible. No clever construction can fix it; you cannot make a group of size $2.5$. Math is annoying like that.

Sufficient condition

If every $c_k$ is divisible by $k$, construction is easy:

1. Store all indices with the same $b_i=k$.
2. Split those indices into chunks of size $k$.
3. Give each chunk a fresh value in $a$.

For example, if the indices with $b_i=3$ are:

$$[2,5,7,9,10,12]$$

then split them as:

$$[2,5,7], [9,10,12]$$

Assign one new value to the first chunk, and another new value to the second chunk. Each of those values appears exactly $3$ times, so every index in those chunks correctly has occurrence count $3$.

Why labels from $1$ to $n$ are enough

Every group gets one fresh label. The total number of groups is:

$$\sum_{k=1}^{n} \frac{c_k}{k}$$

Since $k \ge 1$, this is at most:

$$\sum_{k=1}^{n} c_k = n$$

So we never need more than $n$ distinct labels, and the statement allows all $a_i$ between $1$ and $n$.

Proof of correctness

For each $k$, the algorithm only groups indices whose $b_i=k$. Each group has exactly $k$ indices and receives a unique value. Therefore that value appears exactly $k$ times in $a$.

Now take any position $i$. Suppose $b_i=k$. The algorithm placed $i$ into some chunk of size $k$, and assigned that entire chunk one fresh value $x$. Since $x$ appears exactly on that chunk and nowhere else, $f(x)=k$. Therefore:

$$f(a_i)=f(x)=k=b_i$$

So every position satisfies the requirement.

If the algorithm prints $-1$, then for some $k$, $c_k$ is not divisible by $k$. But every value assigned to positions with $b_i=k$ would need to appear exactly $k$ times, meaning those positions must be partitioned into groups of size $k$. That is impossible when $c_k$ is not divisible by $k$. So printing $-1$ is correct.

Complexity

Each index is stored and assigned once.

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

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