#P17270. [2025年南开中学集训]高塔联络

[2025年南开中学集训]高塔联络

题目描述

有 n n 座塔排成一列,第 i i 座高度为 hi h_i 。

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

第 i i 座可以与 ai a_i 座其他的塔联络,给定 a1,⋯ ,an a_1,\cdots,a_n ,构造一组 h1,⋯ ,hn h_1,\cdots,h_n ,保证有解。

输入格式

第一行一个整数 n n 。

第二行 n n 个整数 a1,⋯ ,an a_1,\cdots,a_n 。

输出格式

一行 n n 个整数 h1,⋯ ,hn h_1,\cdots,h_n 。

你需要保证 1≤hi≤109 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) h=(7,5,7,1,10,4) :

  • 第 1 1 座塔可以和第 2,3,5 2,3,5 座联络
  • 第 2 2 座塔可以和第 1,3,5 1,3,5 座联络
  • 第 3 3 座塔可以和第 1,2,4,5 1,2,4,5 座联络
  • 第 4 4 座塔可以和第 3,5 3,5 座联络
  • 第 5 5 座塔可以和第 1,2,3,4,6 1,2,3,4,6 座联络
  • 第 6 6 座塔可以和第 5 5 座联络

样例2

样例输入

4
3 3 3 3

样例输出

3 2 1 4

样例3~5

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

数据范围

所有数据:

  • 2≤n≤5×105 2\leq n\leq 5\times 10^5
  • 0≤ai≤n−1 0\leq a_i\leq n-1

子任务分布:

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