Recently I was trying out a data structure problem and I couldn't solve it. Can anybody please help me to solve the problem, I would also like to know how to approach such problems.

Problem: You had lost a permutation p={1..N} and want to retrieve it. For each index 1<=i<=N you have the following information

1) The index j of the first number to the left of i such that p[j]>p[i].(It will be 0 if there is no such index)

2) the index j of the first number to the right of i such that p[j]>p[i].(It will be 0 if there is no such index)

The constraint on N is 5*10^5.

If multiple solution exists print the lexicographically smallest permutation.

Sample Input:

5

0 2

0 0

2 0

3 5

3 0

Sample Output: 1 5 4 2 3

Note: 4 5 3 1 2 is also valid but not the lexicographically smallest permutation.