题目描述

有 n 头奶牛，已知它们的身高为 1～n 且各不相同，但不知道每头奶牛的具体身高。 现在这 n 头奶牛站成一列，已知第 i 头牛前面有 Ai 头牛比它低，求每头奶牛的身高。

输入格式

第 1 行：输入整数 n。 第 2 行：n-1个数 Ai（i=2~n），第 i 行表示第 i 头牛前面有 Ai 头牛比它低。 （注意：因为第 1 头牛前面没有牛，所以并没有将它列出）

输出格式

输出 1 行，包含 n 个数，表示 n 头牛的身高。 第 i 行输出第 i 头牛的身高。

样例

输入样例 1

5
1 2 1 0

输出样例 1

2 4 5 3 1

输入样例 2

1

输出样例 2

1

输入样例 3

2
0

输出样例 3

2 1

提示

数据范围：1≤n≤105

思路：我们可以用树状数组维护一个bool数组，数组在 1~n 某个位置是 1 说明现在这个高度的牛还未出现， 而如果是0，说明已经出现了。 从第n头牛开始倒序遍历：假设 n=4， 如果第4头牛前面有1头牛比它低，找bool数组的第二个1出现的位置，那么它的身高应该是2。 此时：1 0 1 1 第 n-1 头牛前面有1有牛比它低，bool数组的第二个1出现的位置，那么它的身高应该是3。 此时：1 0 0 1 ..... 那么我们可以使用一个树状数组来维护，以logn的时间对前缀和进行二分查找，找到目标位置， 而每次利用树状数组求前缀和的时间复杂读也是logn，因此单次操作的时间复杂度为(logn)^2