Proficient.
Put your skills to the test.

Problem summary

Reconstruct a permutation of tower heights 1…N. Tower i covers an earlier shorter tower j when every tower strictly between them is shorter than j. The number covered by each i is given.

Source clarification. The official example is one valid witness. This deterministic topological ordering can output another valid permutation, which the judge accepts.

Constraints

2 ≤ N ≤ 1000000; a solution is guaranteed.

Worked example

An independently prepared example for this explanation.

6
0
1
0
0
0
2

5
6
4
2
1
3

Solution analysis

1. For a known height permutation, a decreasing monotone stack detects coverage: processing i pops exactly the shorter visible towers it covers. Thus the given Li tells us exactly how many stack entries must be popped, even before heights are known.
2. Build inequality edges while simulating those prescribed pops. Each popped vertex must be shorter than i, so add popped→i. If a stack top remains, i must be shorter than that top, so add i→top. Then push i. A topological ordering assigns increasing heights satisfying all inequalities.
3. For counts 0,1,0,0,0,2, the final tower pops towers 5 and 4, forcing both below tower 6; tower 3 remains above it. The sample permutation 5,6,4,2,1,3 satisfies these inequalities. Other topological orders may print different valid heights.

Why it works

The supplied counts come from a real permutation, so the generated inequalities are consistent and their graph is acyclic. Any increasing assignment along a topological order makes the simulated stack strictly decreasing. Exactly the prescribed entries are below each new tower and any surviving top is above it, so actual monotone-stack pops equal Li. Those pops are exactly the covered towers, proving validity.

Watch out. The output is nonunique. Cover counts are not ordinary inversion counts. Use an iterative topological traversal for a million vertices.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<queue>
// Algorithm: For a known height permutation, a decreasing monotone stack detects coverage:
// processing i pops exactly the shorter visible towers it covers.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<vector<int>>next(n);
    vector<int>indegree(n,0),stack,height(n);
    auto edge=[&](int from,int to){
        next[from].push_back(to);
        ++indegree[to];
    };
    for(int i=0;i<n;++i){
        int covered;
        cin>>covered;
        while(covered-->0){
            edge(stack.back(),i);
            stack.pop_back();
        }
        if(!stack.empty()){
            edge(i,stack.back());
        }
        stack.push_back(i);
    }
    queue<int>ready;
    for(int i=0;i<n;++i){
        if(indegree[i]==0){
            ready.push(i);
        }
    }
    int value=0;
    while(!ready.empty()){
        int vertex=ready.front();
        ready.pop();
        height[vertex]=++value;
        for(int to:next[vertex]){
            if(--indegree[to]==0){
                ready.push(to);
            }
        }
    }
    for(int valueAtTower:height){
        cout<<valueAtTower<<'\n';
    }
}