对于样例来说，不可能从前往后求第i头牛的身高，但是从后往前看，思路便会浮现

样例分析 A ={., 0, 1, 2, 1, 0}, 剩余未求出身高的牛：1 2 3 4 5

• A[5] = 0，含义为 前五个数中，没有（0个）比它小的数了，那么它的身高一定是1，剩余未求出身高的牛：2 3 4 5
• A[4] = 1，含义为 剩下的四个数中，有一个比它小的数，那么它是第二小，为3，剩余未求出身高的牛：2 4 5
• A[3] = 2，含义为 剩下三个数中，有两个比它小的数，那么它是第三小，即为5，剩余未求出身高的牛：2 4
• 故 A[2] = 1，含义为 剩下两个数中，它是第二小的，为4，剩余未求出身高的牛：2
• A[1] = 0，代表它是剩余数中最小的，只剩一个2了，所以它的身高为2

所以答案为 2 4 5 3 1
故 A[i] = m 含义是从剩下的i个数中选第m+1小的数，便是第i头牛的身高
那么如何知道剩下的i个数中第m+1小的数是多少呢？

思路

定义树状数组tr[N]维护从1 到 n 的身高是否被选中, 为描述方便，定义数组a[N]代表原数组
- 每个身高是否被选中的状态（1 - n）初始化为1，即add(i, 1), 也就是 fill(a + 1, a + 1 + n, 1);
- 若其中一个身高被选中，则置为0，即add(i, -1), 也就是 a[i] = 0;
- 那么树状数组中query(x) 便是求a[1]到a[x]的前缀和，又因为a[1]到a[x]中的值只能是1或者0，所以query(x)的值为多少就代表着a[1]-a[x]中还有多少个数没被置为0（这个身高还没被选中），即可以求出x 是剩余的1-x中第query(x) 小的数

所以 若 A[4] = 5, 我们只要找到一个最小的x，使得query(x) == 5 + 1, x即为第4头牛的身高

然而从1开始一个一个向后query找x太慢了，发现从1 到 n的query(i) 满足单调且连续的性质，所以这道题目可以用二分求解

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int tr[N];
int n, a[N];

int lowbit(int x){
    return x & -x;
}

void modify(int x, int d){
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += d;
}

int query(int x){
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i ) modify(i, 1);
    for(int i = 2; i <= n; ++i) scanf("%d", &a[i]);

    for(int i = n; i >= 1; --i){
        int m = a[i] + 1;  // 选第m = a[i]+1 小的数
        int l = 1, r = n + 1;
        while(l < r){
            int mid = l + r >> 1;
            if(query(mid) < m) l = mid + 1;
            else r = mid;
        }
        // l 便为要找的 x
        modify(l, -1);
        a[i] = l;
    }

    for(int i = 1; i <= n; ++i) cout << a[i] << endl;

    return 0;
}