题目描述

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

塔和塔可以联络，当且仅当 $\displaystyle\max(h_i,h_j)>\max_{k\in[i+1,j-1]}h_k$ 。例如，相邻塔一定可以联络。

第 $i$ 座可以与 $a_i$ 座其他的塔联络，给定 $a_1,\cdots,a_n$ ，构造一组 $h_1,\cdots,h_n$ ，保证有解。

输入格式

第一行一个整数 $n$ 。

第二行 $n$ 个整数 $a_1,\cdots,a_n$ 。

输出格式

一行 $n$ 个整数 $h_1,\cdots,h_n$ 。

你需要保证 $1\leq h_i\leq 10^9$ 。

样例1

样例输入

6
3 3 4 2 5 1

样例输出

7 5 7 1 10 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$ 座联络

样例2

样例输入

4
3 3 3 3

样例输出

3 2 1 4

样例3~5

见附加的样例文件，分别满足子任务3、子任务4、子任务5的性质。

数据范围

所有数据：

• $2\leq n\leq 5\times 10^5$
• $0\leq a_i\leq n-1$

子任务分布：

• 子任务1（5分）： $n\leq 8$
• 子任务2（5分）： $n\leq 15$
• 子任务3（15分）：保证存在一组 $h_i$ 互不相同的解
• 子任务4（15分）：保证存在一组 $1\leq h_i\leq 2$ 的解
• 子任务5（20分）： $n\leq 100$
• 子任务6（20分）： $n\leq 2\ 000$
• 子任务7（20分）：无特殊限制