题目描述

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.

3
3 1 2

1 3 2

2
2 2

1 1

3
1 4 1

2 1 3

提示

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$
	^	None.
	$1 \le N \le 5 \times 10^6$	The original array $A$ is a permutation.
	^	None.