405902: GYM102155 D Lunch Queue

It is lunch time! That's why n employees are coming to the canteen to have lunch. It is known that i-th employee works in the team c_i and has impudence a_i.

Suppose there are currently l people in the queue. Positions in the queue are numbered from 1 to l from the beginning of the queue. When a person comes to the canteen, he tries to get as close to the beginning of the queue as possible by staying next to one of his teammates. Formally, if a newcomer gets into the queue at the position k (1 ≤ k ≤ l + 1), he shifts the k-th person and everybody behind him one position back and gets the position k. In particular, k = 1 corresponds to the beginning of the queue and k = l + 1 corresponds to the end of the queue.

An employee i can stay at the position k only if two conditions are held:

• After getting to the position k, at least one of the neighbors of newcomer is from the same team c_i;
• A newcomer is not shifting too much people for his level of impudence, namely: k ≥ l + 1 - a_i.

Among all k satisfying the conditions above the minimum possible is chosen. If there are no suitable values of k, a newcomer simply takes place after the last person in the queue.

For example, if there are five people in the queue working in teams 1, 3, 4, 1, 3 respectively (starting from the beginning of the queue) and the newcomer works in team 1 and has impudence 3, he stays at the position 4 of the queue. After that, the sequence of the employee teams becomes 1, 3, 4, 1, 1, 3. Note that impudence value of 3 also allowed him to get to the position 3, but there would be no teammates next to him in that case, so the first condition is violated.

Knowing the order in which employees arrive and their values of c_i and a_i, find out how the queue will look like in the end.

The first line contains an integer n (1 ≤ n ≤ 400 000), the number of employees.

Each of the next n lines contains two integers c_i, a_i (1 ≤ c_i ≤ n, 0 ≤ a_i ≤ 400 000), the team and the impudence of the i-th employee.

Output n distinct integers from 1 to n which are the indices of people in the queue from beginning of the queue to the end after all employees get to the canteen. Employees are indexed from 1 to n in order of their appearance in the input data.

8
1 0
2 1
2 2
1 1
3 2
1 3
2 3
2 5

1 3 8 2 7 6 4 5