Mike and code of a permutation
Contest: Codeforces Round 410 (Div. 2)
Difficulty rating: 3000
Tags: constructive algorithms, data structures, graphs, sortings

Mike has discovered a new way to encode permutations. If he has a permutation P = [p1, p2, ..., pn], he will encode it in the following way:

Denote by A = [a1, a2, ..., an] a sequence of length n which will represent the code of the permutation. For each i from 1 to n sequentially, he will choose the smallest unmarked j (1 ≤ j ≤ n) such that pi < pj and will assign to ai the number j (in other words he performs ai = j) and will mark j. If there is no such j, he'll assign to ai the number  - 1 (he performs ai =  - 1).

Mike forgot his original permutation but he remembers its code. Your task is simple: find any permutation such that its code is the same as the code of Mike's original permutation.

You may assume that there will always be at least one valid permutation.

Input format:
The first line contains single integer n (1 ≤ n ≤ 500 000) — length of permutation.

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ n or ai =  - 1) — the code of Mike's permutation.

You may assume that all positive values from A are different.

Output format:
In first and only line print n numbers p1, p2, ..., pn (1 ≤ pi ≤ n) — a permutation P which has the same code as the given one. Note that numbers in permutation are distinct.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
For the permutation from the first example:

i = 1, the smallest j is 2 because p2 = 6 > p1 = 2.

i = 2, there is no j because p2 = 6 is the greatest element in the permutation.

i = 3, the smallest j is 1 because p1 = 2 > p3 = 1.

i = 4, the smallest j is 5 (2 was already marked) because p5 = 5 > p4 = 4.

i = 5, there is no j because 2 is already marked.

i = 6, the smallest j is 4 because p4 = 4 > p6 = 3.

Example input:
6
2 -1 1 5 -1 4

Example output:
2 6 1 4 5 3

Example input:
8
2 -1 4 -1 6 -1 8 -1

Example output:
1 8 2 7 3 6 4 5

Editorial:
Let's consider ai = n + 1 instead of ai =  - 1. Let's also define the sequence b, bi = j such that aj = i or bi = n + 1 if there is no such j. Lets make a directed graph with vertices be the indices of the permutation p with edges of type (a, b) representing that pa < pb. If we topologically sort this graph then we can come up with a possible permutation,if S is the topologically sorted graph then we can assign to pSi number i (in other words pSi = i). But how we can find the edges? First of all there are edges of form (bi, i) if bi ≠ n + 1.For a vertex i he visited all the unmarked vertices j (1 ≤ j < ai, j ≠ i) and you know for sure that for all these j,pj < pi. But how we can check if j was already marked? The vertex j will become marked after turn of vertex bj or will never become unmarked if bj = n + 1. So there is a direct edge from i to j if j = ai or 1 ≤ j < ai, j ≠ i and bj > i. The main problem is to extract j for a given i in a sub-quadratic time,the solution is segment tree and is based on the fact that each time we want to extract vertex j from all non-visited edges (1 ≤ j < ai,j ≠ i) with maximal bj,if bj < i then there aren't remaining edges.
Complexity and memory are $${\mathcal O}(N\log N)$$ and O(N).