H. High Towers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ towers in a row. The height of the $$$i$$$-th tower is $$$h_i$$$.

Towers can communicate with each other if one of them is higher than all the towers between them. More formally, towers $$$i$$$ and $$$j$$$ ($$$i \lt j$$$) can communicate with each other if and only if $$$max(h_i, h_j) \gt max_{k \in [i+1, j-1]} h_k$$$. Note that adjacent towers always can communicate with each other.

For each tower, we know the value $$$a_i$$$  — with how many other towers can $$$i$$$-th tower communicate. Find any possible sequence of heights $$$h_i$$$, $$$1 \le i \le n$$$.

It's guaranteed that in all provided tests there exists at least one possible sequence of heights. If there are multiple possible answers output any of them.

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$)  — the number of towers.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n-1$$$)  — the number of towers that can communicate with $$$i$$$-th tower.

Output

In a single line output $$$n$$$ integers $$$h_i$$$ ($$$1 \le h_i \le 10^9$$$).

It's guaranteed that in all provided tests at least one possible sequence of $$$h_i$$$ exists. If there are multiple possible answers output any of them.

Examples
Input
6
3 3 4 2 5 1
Output
7 5 7 1 10 4
Input
4
3 3 3 3
Output
3 2 1 4
Note

In the first sample, for $$$h = [7, 5, 7, 1, 10, 4]$$$:

  • Tower $$$1$$$ can communicate with towers $$$2, 3, 5$$$
  • Tower $$$2$$$ can communicate with towers $$$1, 3, 5$$$
  • Tower $$$3$$$ can communicate with towers $$$1, 2, 4, 5$$$
  • Tower $$$4$$$ can communicate with towers $$$3, 5$$$
  • Tower $$$5$$$ can communicate with towers $$$1, 2, 3, 4, 6$$$
  • Tower $$$6$$$ can communicate with tower $$$5$$$