CF309E Sheep

信息技术正在飞速发展，并日益渗透到人类活动的各个领域。令人难以置信的是，最现代的信息技术甚至被应用在了农业上！ 一个大型牧场上有一片草地，羊群正在上面吃草。共有 $n$ 只羊，每只羊都被编号为 1 到 $n$ —— 因为羊的外观很相似，必须用编号加以区分并记录信息！牧场的草地被分成编号为 1 到无穷大的若干区域。已知第 $i$ 只羊喜欢编号从 $l_i$ 到 $r_i$ 的所有区域。 有两位牧羊人照看这些羊：First 和 Second。First 很早起床，带着羊群去草地上吃草。Second 傍晚时分赶来，把所有羊赶回。 某天早晨，First 起晚了，没有时间带羊群到草地上吃草。他于是采取了措施：只要两只羊有喜欢的区域重叠，就将它们捆绑在一起。First 认为这样做比较好——到晚上，Second 收羊时会轻松些，因为被拴在一起的羊不容易各自跑开！ 傍晚，Second 来到草地上，集合了所有的羊，打算让它们排成一排。可是，无论他如何尝试，羊群总是无法满足 Second 的排列要求！Second 既没有力气，也无法解开羊群之间的绳索，于是他只好妥协，但提出了一个条件：他希望能让被绑在一起的两只羊排在队列中的最大距离尽可能小。两只羊之间的距离定义为它们之间队列中间的羊的数量。 请帮 Second 找出一种羊的排列方式，使得被捆绑在一起的两只羊在队列中的最大距离最小。

第一行输入一个整数 $n$（$1 \leq n \leq 2000$）。接下来的 $n$ 行，每行两个整数 $l_i$ 和 $r_i$（$1 \leq l_i, r_i \leq 10^9$，$l_i \leq r_i$）。

输出 $n$ 个用空格分隔的整数，表示满足条件的某种羊的排列顺序。第 $i$ 个数表示排在第 $i$ 个位置的羊的编号。 如果有多种最优排列，输出任意一种均可。

由 ChatGPT 5 翻译