High Towers#12940

High Towers

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.

Input

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.

Output

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.

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

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