409544: GYM103627 H Endless Road

Whenever students of KAIST go outside of campus, they usually follow a straight road named the Endless Road. The name comes from the fact that most students feel like the road is endless. One factor for this is due to the boring scenery of the road. Here, we model the Endless Road as a straight line of length $$$10^9$$$. The position over the straight line can be denoted as a single real number $$$x \in [0, 10^9)$$$.

To cope with this, the members of RUN@KAIST decided to plant different kinds of colorful flowers along this road. The $$$N$$$ members of RUN@KAIST are numbered from $$$1$$$ to $$$N$$$. In the last regular meeting, each member was assigned a nonempty segment $$$[L_i, R_i)$$$ over the straight line, containing all positions $$$x$$$ such that $$$L_i \le x < R_i$$$.

The members with higher indices bear more responsibility for the tasks on the club. Thus, the length of the segments is nondecreasing as the indices of the members increase. In other words, $$$R_i - L_i \leq R_j - L_j$$$ for $$$1 \le i < j \le N$$$.

The planting is done in $$$N$$$ turns. In each turn, we select one previously unselected member to plant flowers. The selected member plants the flowers in their assigned segment $$$[L_i, R_i)$$$, except where other members have already planted flowers before.

To make the work distribution more equitable, the selection is done in the following way:

• Pick the member who will plant the minimum number of flowers. Here, the number of flowers is determined by the total length of the intervals where this member will plant new flowers, which could be zero.
• If there is more than one such member, pick the member with minimum index.

Jaeung should now announce the planting schedule. For this, he has to find an order in which the $$$N$$$ members will plant the flowers, according to the above selection rules. Please help him do it.

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 250\,000$$$).

The next $$$N$$$ lines each contain two integers $$$L_i$$$ and $$$R_i$$$ ($$$0 \le L_i < R_i \le 10^9$$$, $$$R_i - L_i \leq R_j - L_j$$$ for all $$$1 \le i < j \le N$$$).

All intervals are distinct. In other words, $$$(L_i, R_i) \neq (L_j, R_j)$$$ for all $$$1 \le i < j \le N$$$.

Output $$$N$$$ integers denoting the order of planting. The $$$i$$$-th integer denotes the index of the member who will plant flowers in the $$$i$$$-th turn.

6
1 2
2 3
3 4
4 5
1 3
3 5

1 2 5 3 4 6 

4
3 7
10 14
1 6
6 11

1 3 2 4