如果整数数组 $$$p_{1},p_{2}, \ldots,p_{n}$$$ 包含从 $$$1$$$ 到 $$$n$$$ 的每个数字恰好一次,则称为排列。例如,以下数组是排列:$$$[3,1,2]、[1]、[1,2,3,4,5]$$$ 和 $$$[4,3,1,2]$$$。以下数组不是排列:$$$[2], [1,1], [2,3,4]$$$。
存在长度 $$$n$$$ 的隐藏排列。
对于每个索引 $$$i$$$,您将得到 $$$s_{i}$$$,它等于所有 $$$p_{j}$$$ 的总和,使得 $$$j < i$$$ 且 $$$p_{j} < p_{i}$$$。换句话说,$$$s_i$$$是第$$$i$$$之前小于第$$$i$$$元素的元素之和。
你的任务是恢复排列。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$) — 排列的大小。
第二行包含 $$$n$$$ 整数 $$$s_{1}, s_{2}, \ldots, s_{n}$$$ ($$$0 \le s_{i} \le \frac{n(n-1)}{2}$$$)。
保证数组 $$$s$$$ 对应于长度 $$$n$$$ 的有效排列。
输出
打印 $$$n$$$ 整数 $$$p_{1}, p_{2}, \ldots, p_{n}$$$ — 恢复排列的元素。我们可以证明答案总是唯一的。
示例
输入 #1
3 0 0 0
输出 #1
3 2 1
输入 #2
2 0 1
输出 #2
1 2
输入 #3
5 0 1 1 1 10
输出 #3
1 4 3 2 5
注意
在第一个示例中,对于每个$$$i$$$,没有满足这两个条件的索引$$$j$$$,因此$$$s_i$$$ 始终为$$$0$$$。
在 $$$i = 2$$$ 的第二个示例中,$$$j = 1$$$ 满足条件,因此 $$$s_2 = p_1$$$。
在 $$$i = 2, 3, 4$$$ 的第三个示例中,只有 $$$j = 1$$$ 满足条件,因此 $$$s_2 = s_3 = s_4 = 1$$$。对于 $$$i = 5$$$,所有 $$$j = 1, 2, 3, 4$$$ 都是可能的,因此 $$$s_5 = p_1 + p_2 + p_3 + p_4 = 10$$$。