Canadian Computing Olympiad 2026: Day 1, Problem 2

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\leq i\leq r~ and $$\displaystyle 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.

Input Specification

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\leq B[i]\leq N^2~).

The following table shows how the 25 available marks are distributed:

Marks Awarded	Bounds on ~N~	Additional Constraints
2 marks	~1\leq N\leq 8~	None.
3 marks	~1\leq N\leq 5\,000~	The original array ~A~ is a permutation.
5 marks	~1\leq N\leq 3\times 10^5~	The original array ~A~ is a permutation.
5 marks		None.
5 marks	~1\leq N\leq 5\times 10^6~	The original array ~A~ is a permutation.
5 marks		None.

Output Specification

Output ~N~ space-separated integers, the array ~A[1],\ldots,A[N]~, where ~1\leq A[i]\leq 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.

Sample Input 1

3
3 1 2

Sample Output 1

1 3 2

Explanation for Sample Output 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.

Sample Input 2

2
2 2

Sample Output 2

1 1

Sample Input 3

3
1 4 1

Sample Output 3

2 1 3

Explanation for Sample Output 3

Note that ~A = [2, 1, 2]~ would also be accepted by the judge.