← 返回题目列表

Codeforces · 309/E

E. 羊

中文机器翻译题面 查看原题

信息技术正在发展并日益渗透到人类活动的各个领域。令人难以置信的是,最现代的技术被用于农业!

一个大农场有一个草地,里面有放牧的羊。总共有 n 只羊,每只羊都包含一个从 1 到 n 的唯一数字 - 因为需要区分羊,你需要记住每只羊的信息,而且它们非常相似!草地由无数个区域组成,编号从 1 到无穷大。已知羊i喜欢里到里的区域。

有两个牧羊人在照顾羊:第一和第二。一大早起床,牵着羊群在草坪上吃草。第二次在晚上来收集所有的羊。

一天早上,先比平时起得晚了一点,没时间牵羊到草坪上吃草。因此,如果有两个羊都喜欢的地区,他就把每两只羊绑在一起。一是觉得这样会好一点——二是晚上的工作量会少一些,因为羊不会散太多,互相拴着!

晚上,第二个来到草坪上,聚集羊群并试图将它们排成一排。但无论他如何努力,羊都不会按照老二的意愿排列!老二既没有力气,也没有能力解开羊群,所以他就让羊群保持原状,但有一个条件:他要把羊排成一排,使两只被绑住的羊之间的最大距离尽可能小。羊之间的距离是介于两者之间的行中羊的数量。

帮助第二找到正确的安排。

输入

第一个输入行包含一个整数 n (1 ≤ n ≤ 2000)。以下 n 行中的每一行包含两个整数 li 和 ri (1 ≤ li, ri ≤ 109; li ≤ ri)。

输出

在单个输出行中打印 n 个空格分隔的数字 - 所寻求的羊的排列。该行中的第 i 个值必须代表最优排列行中从左起第 i 个位置的羊的数量。

如果有多个最佳排列,则打印其中任意一个。

示例

输入 #1

3
1 3
5 7
2 4

输出 #1

1 3 2

输入 #2

5
1 5
2 4
3 6
1 7
2 6

输出 #2

2 1 3 5 4

输入 #3

4
1 3
4 6
5 7
2 3

输出 #3

1 4 2 3