#P18465. High Towers

High Towers

High Towers

有 nn 座塔排成一行,第 ii 座塔的高度为 hih_i。

如果两座塔中至少有一座比它们之间的所有塔都高,那么它们可以互相通信。准确地说,对于 i<ji<j,当且仅当

max⁡(hi,hj)>max⁡i<k<jhk\max(h_i,h_j)>\max_{i<k<j}h_k

时,第 ii 座塔和第 jj 座塔能够通信。相邻的两座塔总是能够通信。这里比较使用严格的大于号;高度允许相等,即允许重复高度。

对于每座塔,已知 aia_i:它能与其他多少座塔通信。求任意一个可能的高度序列 h1,h2,…,hnh_1,h_2,\ldots,h_n。

保证输入中的每个测试都至少存在一种合法的高度序列。如果有多个答案,可以输出任意一个。

输入格式

第一行包含整数 nn(2≤n≤5⋅1052\le n\le5\cdot10^5),表示塔的数量。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai≤n−10\le a_i\le n-1),表示各塔能够与其他多少座塔通信。自身不计入 aia_i。

输出格式

在一行中输出 nn 个整数 h1,h2,…,hnh_1,h_2,\ldots,h_n,要求 1≤hi≤1091\le h_i\le10^9,且按照上述通信规则得到的每个度数都恰等于输入的 aia_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

原样例说明

第一个样例的高度为 [7,5,7,1,10,4][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 座塔通信。