P16902 [CCO 2026] Melborp

本题测试数据过大，评测时需要 2-4 分钟加载测试数据。因为测试数据过大，洛谷无法支持该题的数据下载。

Seta 正在为 CCO 出题！她想到了如下问题： 给定一个值域在 $[1, N]$ 的数组 $A[1,\ldots,N]$，定义 $B[i]$ 为满足 $\ell \le i \le r$ 且 $A[i] = \min(A[\ell], A[\ell + 1], \ldots, A[r - 1], A[r])$ 的二元组 $(\ell, r)$ 的个数。 输出数组 $B[1,\ldots,N]$。 然而，就在 CCO 的前一天，Seta 的电脑崩溃了，她只恢复了输出文件。给定输出数组 $B[1,\ldots,N]$，你能否编写一个程序，重新构造出输入数组 $A[1,\ldots,N]$ 呢？ Seta 提醒你，数组 $A$ 并不唯一，任何合法的数组都会被她接受。

输入的第一行包含一个整数 $N$。第二行包含 $N$ 个以空格分隔的整数 $B[1],\ldots,B[N]$ ($1 \le B[i] \le N^2$)。

输出 $N$ 个以空格分隔的整数，即数组 $A[1],\ldots,A[N]$，其中 $1 \le A[i] \le N$。数据保证至少存在一个合法的数组 $A$。 如果存在多个合法数组，你可以输出其中任意一个。特别地，即使原始的数组 $A$ 是一个排列，你的答案也不必是排列。

**样例输入 1 的输出解释** - 子数组 $[1,3,2]$、$[1,3]$、$[1]$ 的最小值均为 $1$。满足条件的子数组有 $3$ 个。 - 子数组 $[3]$ 的最小值为 $3$。满足条件的子数组有 $1$ 个。 - 子数组 $[3,2]$ 和 $[2]$ 的最小值均为 $2$。满足条件的子数组有 $2$ 个。 **样例输入 3 的输出解释** 注意，$A = [2,1,2]$ 同样会被评测机接受。 下面的表格展示了可获得的 $25$ 分的分配情况： | 分值 | $N$ 的范围 | 额外限制 | |:-:|:-:|:-:| | $2$ 分 | $1 \le N \le 8$ | 无。 | | $3$ 分 | $1 \le N \le 5\,000$ | 原始数组 $A$ 是一个排列。 | | $5$ 分 | $1 \le N \le 3 \times 10^5$ | ^ | | $5$ 分 | ^ | 无。 | | $5$ 分 | $1 \le N \le 5 \times 10^6$ | 原始数组 $A$ 是一个排列。 | | $5$ 分 | ^ | 无。 | 翻译由 DeepSeek V4 Pro 完成