Có N (2 ≤ N ≤ 8.000) con bò có mã số riêng biệt trong khoảng từ 1 đến N. Trong một hành động thiếu suy nghĩ, chúng đã ghé thăm cái "bể nước" gần nhà và uống hơi quá nhiều bia trước bữa tối. Khi đến lúc xếp hàng để ăn tối, chúng không xếp theo thứ tự tăng dần của mã số.

Thật tiếc là FJ không có cách nào để sắp xếp chúng. Hơn nữa, ông ấy cũng không giỏi quan sát vấn đề. Thay vì ghi lại mã số của từng con bò, ông đã tính một thống kê hơi ngốc: Với mỗi con bò trong hàng, ông biết có bao nhiêu con bò đứng trước nó mà có mã số nhỏ hơn nó.

Cho dữ liệu này, hãy giúp FJ xác định thứ tự chính xác của các con bò.

Đầu vào

• Dòng 1: Một số nguyên duy nhất N
• Dòng 2 đến N: N-1 dòng mô tả số lượng con bò đứng trước một con bò trong hàng mà có mã số nhỏ hơn nó. Rõ ràng, không có con bò nào đứng trước con đầu tiên, nên nó không được liệt kê. Dòng 2 mô tả số lượng con bò trước con thứ hai có mã số nhỏ hơn nó; dòng 3 mô tả số lượng con bò trước con thứ ba có mã số nhỏ hơn nó; v.v.

Đầu ra

• Dòng 1 đến N: Mỗi dòng chứa mã số của một con bò trong hàng. Dòng 1 chứa mã số của con bò đầu tiên trong hàng; dòng 2 chứa mã số của con bò thứ hai; v.v.

Ví dụ

<strong>Đầu vào:</strong>
5
1
2
1
0

<strong>Đầu ra:</strong>
2
4
5
3
1

Phân tích

Từ ví dụ ta thấy, con bò đầu tiên không có ai đứng trước, nên dữ liệu đầu vào bắt đầu từ con thứ hai.

Để xác định thứ tự dễ dàng hơn, ta sẽ tính ngược từ cuối về đầu. Con bò cuối cùng có 0 con bò đứng trước có mã số nhỏ hơn, nên mã số của nó là số nhỏ nhất còn trống.

Gọi mảng f[i] = 1 nếu vị trí i chưa được sử dụng, f[i] = 0 nếu đã dùng. Ban đầu tất cả đều là 1.

Giả sử con bò thứ i từ cuối có a[i] con bò đứng trước có mã số nhỏ hơn, thì vị trí của nó là vị trí thứ a[i]+1 trong các vị trí còn trống (tức là các vị trí f[j] = 1).

Chẳng hạn với con bò cuối cùng a[i] = 0, ta tìm vị trí thứ 1 trong các vị trí còn trống → vị trí 1 → gán f[1] = 0.

Với con bò trước đó a[i] = 1, ta tìm vị trí thứ 2 trong các vị trí còn trống → vị trí 3 → gán f[3] = 0.

Giải pháp

Sử dụng cấu trúc dữ liệu BIT (Binary Indexed Tree) để tính nhanh tổng tiền tố và tìm vị trí cần thiết.

Mỗi lần tìm vị trí thứ k trong các vị trí còn trống, ta dùng tìm kiếm nhị phân trên tổng tiền tố. Nếu tổng tiền tố tại vị trí x bằng k, thì x là vị trí thứ k.

Code minh họa:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

inline ll read() {
    ll a = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') {a = a * 10 + c - '0'; c = getchar();}
    return a * f;
}

const int MAXN = 100010;
ll n, a[MAXN], bit[MAXN], ans[MAXN];

inline ll lowbit(ll x) {
    return x & (-x);
}

inline void update(ll x, ll val) {
    while (x <= n) {
        bit[x] += val;
        x += lowbit(x);
    }
}

inline ll query(ll x) {
    ll res = 0;
    while (x) {
        res += bit[x];
        x -= lowbit(x);
    }
    return res;
}

inline ll find_kth(ll k) {
    ll left = 1, right = n;
    while (left < right) {
        ll mid = (left + right) >> 1;
        if (query(mid) < k)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

int main() {
    n = read();
    for (ll i = 2; i <= n; ++i)
        a[i] = read();

    // Khởi tạo BIT với tất cả giá trị là 1
    for (ll i = 1; i <= n; ++i)
        update(i, 1);

    // Tính từ cuối về đầu
    for (ll i = n; i >= 1; --i) {
        ll pos = find_kth(a[i] + 1);
        update(pos, -1);  // Đánh dấu vị trí đã dùng
        ans[i] = pos;
    }

    for (ll i = 1; i <= n; ++i)
        printf("%lld\n", ans[i]);

    return 0;
}