P16902 [CCO 2026] Melborp

Seta is creating problems for the CCO! She came up with the following problem: Given an array $A[1,\ldots,N]$ whose values are in the range $[1,N]$, define $B[i]$ to be the number of pairs $(\ell,r)$ such that $\ell \le i \le r$ and $A[i] = \min(A[\ell], A[\ell + 1], \ldots, A[r - 1], A[r])$. Print the array $B[1,\ldots,N]$. However, the day before the CCO, Seta’s computer crashed, and she was only able to recover the output files. Given the output array $B[1,\ldots,N]$, can you write a program to reconstruct the input array $A[1,\ldots,N]$? Seta reminds you that the array $A$ is not necessarily unique, and she will accept any valid array.

The first line of input will contain a single integer, $N$. The second line of input will contain $N$ space-separated integers $B[1],\ldots,B[N]$ ($1 \le B[i] \le N^2$).

Output $N$ space-separated integers, the array $A[1],\ldots,A[N]$, where $1 \le A[i] \le N$. It is guaranteed that there will always exist at least one valid array $A$. If there is more than one valid array, you may output any valid array. In particular, even if the original array $A$ is a permutation, your answer does not have to be a permutation.

**Explanation of Output for Sample Input $1$** - The subarrays $[1,3,2]$, $[1,3]$, $[1]$ have minimum $1$. There are $3$ such subarrays. - The subarray $[3]$ has minimum $3$. There is $1$ such subarray. - The subarrays $[3,2]$ and $[2]$ have minimum $2$. There are $2$ such subarrays. **Explanation of Output for Sample Input $3$** Note that $A = [2,1,2]$ would also be accepted by the judge. The following table shows how the $25$ available marks are distributed: | Marks Awarded | Bounds on $N$ | Additional Constraints | |:-:|:-:|:-:| | $2$ marks | $1 \le N \le 8$ | None. | | $3$ marks | $1 \le N \le 5\,000$ | The original array $A$ is a permutation. | | $5$ marks | $1 \le N \le 3 \times 10^5$ | The original array $A$ is a permutation. | | $5$ marks | ^ | None. | | $5$ marks | $1 \le N \le 5 \times 10^6$ | The original array $A$ is a permutation. | | $5$ marks | ^ | None. |