#5748. 「CCO 2026」Melborp

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

译自 CCO 2026 Day1 T2「Melborp」。

Seta 正在为 CCO 命题！她想到了下面这个题目：

给定一个数组 $A[1, \dots, N]$，其元素取值范围在 $[1, N]$ 之间。定义 $B[i]$ 为满足 $\ell \le i \le r$ 且 $\min(A[\ell, \dots, r]) = A[i]$ 的数对 $(\ell, r)$ 的数量。 输出数组 $B[1, \dots, N]$。

然而，就在 CCO 开始的前一天，Seta 的电脑死机了，她只找回了输出文件。现在给定输出数组 $B[1, \dots, N]$，你能编写一个程序来还原输入数组 $A[1, \dots, N]$ 吗？

Seta 提醒你，数组 $A$ 不一定是唯一的，她会接受任何合法的数组。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个由空格隔开的整数 $B[1], \dots, B[N]$ $(1 \le B[i] \le N^2)$。

输出格式

输出 $N$ 个由空格隔开的整数，即数组 $A[1], \dots, A[N]$，其中 $1 \le A[i] \le N$。保证至少存在一个合法的数组 $A$。

如果存在多个合法的数组，你可以输出其中任何一个。特别地，即使原始数组 $A$ 是一个排列，你的答案也不一定必须是排列。

样例 1

输入

3
3 1 2

输出

1 3 2

子数组 $[1, 3, 2], [1, 3], [1]$ 的最小值为 $1$。共有 $3$ 个这样的子数组。

子数组 $[3]$ 的最小值为 $3$。共有 $1$ 个这样的子数组。

子数组 $[3, 2]$ 和 $[2]$ 的最小值为 $2$。共有 $2$ 个这样的子数组。

样例 2

输入

2
2 2

输出

1 1

样例 3

输入

3
1 4 1

输出

2 1 3

请注意，数组 $A = [2, 1, 2]$ 也会被评测系统接受。

数据范围与提示

详细子任务附加限制及分值如下表所示。