You are given towers in a row. The height of the -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 and (i < j) can communicate with each other if and only if max(h_i, h_j)>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 -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.
The first line contains a single integer (2 \le n \le 5 \cdot 10^5) — the number of towers.
The second line contains integers a_1, a_2, \ldots, a_n (0 \leq a_i \leq n-1) — the number of towers that can communicate with -th tower.
In a single line output 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.
Example
Example 1
In the first sample, for h = [7, 5, 7, 1, 10, 4]:
Tower can communicate with towers
Tower can communicate with towers
Tower can communicate with towers 1, 2, 4, 5
Tower can communicate with towers
Tower can communicate with towers 1, 2, 3, 4, 6
Tower can communicate with tower