21769번 - 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 on this road. $N$ members of RUN@KAIST are numbered from 1ドル \ldots N$. In the last regular meeting, each member is assigned a nonempty segment over the straight line $[L_i, R_i),ドル containing all positions $L_i \le x < R_i$.

The member with a higher index bears more responsibility for the tasks on the club. Thus, the length of the segment is nondecreasing as the indices of the members increases. 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 amount of flowers. Here, the amount of flowers are determined by the length of the interval where a member planted 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.

입력

The first line contains an integer $N$.

The next $N$ lines each contain two integers $L_i$ and $R_i$.

출력

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

제한

• 1ドル \leq N \leq 250,000円$
• 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$.

서브태스크 1 (7점)

This subtask has an additional constraint.

• $N \le 100$
• $R_i \le 100$ for all 1ドル \le i \le N$

서브태스크 2 (9점)

This subtask has an additional constraint.

• $N \le 10,000円$

서브태스크 3 (17점)

This subtask has an additional constraints.

• There is no pair of members 1ドル \le i, j \le N$ such that $i \neq j,ドル $L_i < L_j,ドル $R_j < R_i$.

서브태스크 4 (13점)

This subtask has an additional constraints.

• There is no pair of members 1ドル \le i, j \le N$ such that $i \neq j,ドル $L_i < L_j < R_i < R_j$.

서브태스크 5 (54점)

This subtask has no additional constraints.

힌트