有 $n$ 座塔排成一排。第 $i$ 座塔的高度为 $h_i$。

如果两座塔中的其中一座比它们之间的所有塔都要高，那么这两座塔就可以互相通信。更正式地说，塔 $i$ 和塔 $j$ ($i < j$) 可以互相通信，当且仅当 $\max(h_i, h_j) > \max_{k \in [i+1, j-1]} h_k$。注意，相邻的塔总是可以互相通信。

对于每一座塔，我们已知值 $a_i$，表示第 $i$ 座塔可以与多少座其他塔通信。请找出一个满足条件的塔高序列 $h_i$ ($1 \le i \le n$)。

题目保证在所有提供的测试用例中，至少存在一个可能的塔高序列。如果存在多个可能的答案，输出其中任意一个即可。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 5 \cdot 10^5$)，表示塔的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n - 1$)，表示第 $i$ 座塔可以通信的塔的数量。

输出格式

在一行中输出 $n$ 个整数 $h_i$ ($1 \le h_i \le 10^9$)。

题目保证在所有提供的测试用例中，至少存在一个可能的 $h_i$ 序列。如果存在多个可能的答案，输出其中任意一个即可。

样例

样例输入 1

6
3 3 4 2 5 1

样例输出 1

7 5 7 1 10 4

样例输入 2

4
3 3 3 3

样例输出 2

3 2 1 4

说明

在第一个样例中，对于 $h = [7, 5, 7, 1, 10, 4]$：

• 塔 1 可以与塔 2, 3, 5 通信
• 塔 2 可以与塔 1, 3, 5 通信
• 塔 3 可以与塔 1, 2, 4, 5 通信
• 塔 4 可以与塔 3, 5 通信
• 塔 5 可以与塔 1, 2, 3, 4, 6 通信
• 塔 6 可以与塔 5 通信