恢复排列(Restore Permutation)

题目描述

小 Z 有一个长度为 $n$ 的全排列数组 $P=[p_1,p_2,\cdots,p_n]$，但是健忘的小 Z 已经忘记了排列的样子。

不过小 Z 记录了一个 $sum[]$ 数组，其中 $sum[i]=\sum_{j=1}^{i-1}[p_j<p_i]p_j$，通俗一点来讲，$sum[i]$ 表示所有 $1\le j < i$ 并且满足 $p_j<p_i$ 的 $p_j$ 的和。

举个例子：

当 $P=[1,4,3,2,5]$ 时，$sum[1]=0$, $sum[2]=p_1=1$, $sum[3]=p_1=1$, $sum[4]=p_1=1$, $sum[5]=p_1+p_2+p_3+p_4=10$。

现在，小 Z 想要你根据这个 $sum[]$ 数组求出原来的排列 $P$。

输入格式

第一行输入一个整数 $n$ 表示排列长度。

接下来一行有 $n$ 个整数，分别为 $sum_1,sum_2,\cdots,sum_n$。

输出格式

输出一行 $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

数据范围

$1\le n \le 2*10^5,0\le sum_i \le \frac{n(n-1)}{2}$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接