← 返回题目列表

Codeforces · 38/G

G. 队列

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

在一个寒冷的冬夜,我们的英雄 Vasya 站在铁路队列中购买 Codeforces 冠军决赛的门票。与往常一样,收银员说他要离开 5 分钟,然后就离开了一个小时。然后Vasya为了不觉得无聊,开始分析队列这样的机制。这一发现让瓦夏大吃一惊。

每个人都有两个数字来表征:ai,这是他当前任务的重要性(数字越大,任务越重要)和数字ci,这是他良心的写照。数字 ai 形成从 1 到 n 的数字排列。

设队列目前由 n - 1 个人组成。让我们看看第 n 号来的人的行为方式。首先,他站在队列的末尾,并执行以下操作:如果他前面的人的任务 ai 的重要性小于 an,则他们交换位置(看起来像这样:编号为 n 的人问他前面的人:“呃……请原谅,但这对我来说非常重要……你能让我在队列中移动吗?”),然后他再次向他前面的人提出问题,依此类推。但如果 ai 大于 an,则队列停止向上移动。然而,编号为n的人最多可以执行cn次操作。

在我们的任务中,我们假设当 n 号加入队列时,n - 1 之间的交换过程将停止。如果交换是可能的,那么它必然会发生。

你的任务是帮助 Vasya 对所描述的过程进行建模,并找到当所有交换停止时人们排队的顺序。

输入

第一个输入行包含一个整数 n,它是加入队列的人数 (1 ≤ n ≤ 105)。在接下来的 n 行中,按照人们到来的顺序给出了对人的描述 - 空格分隔的整数 ai 和 ci (1 ≤ ai ≤ n, 0 ≤ ci ≤ n)。每个描述都位于单行中。所有的ai都是不同的。

输出

输出从1到n的数字排列,表示按照上述规则从头到尾形成的队列。在这个序列中,第 i 个数字代表交换结束后将在第 i 个位置排队的人的号码。人员按照输入中给出的顺序从 1 开始编号。用空格分隔数字。

示例

输入 #1

2
1 0
2 1

输出 #1

2 1

输入 #2

3
1 3
2 3
3 3

输出 #2

3 2 1

输入 #3

5
2 3
1 4
4 3
3 1
5 2

输出 #3

3 1 5 4 2