#2669. 奇怪的队列

奇怪的队列

题目描述

nodgd\red{nodgd}的粉丝太多了,每天都会有很多人排队要签名。

今天有n\red{n}个人排队,每个人的身高都是一个整数,且互不相同。很不巧,nodgd\red{nodgd}今天去忙别的事情去了,就只好让这些粉丝们明天再来。同时nodgd\red{nodgd}提出了一个要 求,每个人都要记住自己前面与多少个比自己高的人,以便于明天恢复到今天的顺序。

但是,粉丝们或多或少都是有些失望的,失望使她们晕头转向、神魂颠倒,已经分不清楚哪一边是"前面"了,于是她们可能是记住了前面比自己高的人的个数,也可能是记住了后面比自己高的人的个数,而且他们不知道自己记住的是哪一个方向。

nodgd\red{nodgd}觉得,即使这样明天也能恢复出一个排队顺序,使得任意一个人的两个方向中至少有一个方向上的比他高的人数和他记住的数字相同。可惜n\red{n}比较大,显然需要写个程序来解决,nodgd\red{nodgd}很忙,写程序这种事情就交给你了。

输入格式

第一行输入一个整数n\red{n},表示指令的条数。

接下来n\red{n}行,每行两个整数ai,bi\red{ai,bi} ,表示一个人的身高和她记住的数字,保证身高互不相同。

输出格式

输出一行,这个队列里从前到后的每个人的身高。

如果有多个答案满足题意,输出字典序最小。

如果不存在满足题意的排列,输出"impossible\red{impossible}"(不含引号)。

样例

输入样例1

4

4 1

3 1

6 0

2 0

输出样例1

2 4 3 6

输入样例2

6

1 5

8 0

3 1

4 0

2 0

6 0

输出样例2

1 2 4 3 6 8

提示

数据范围

n<=100000\red{n<=100000}

ai<=109\red{ai<=10^9}

样例1\red{1}解释

在所给出的答案队列中,第一个人身高为2\red{2,}前面有0\red{0}个人比他高,所以他是输入的第4\red{4}个人;第二个人身高为4\red{4,}右边有1\red{1}个人比他高,所以他是输入的第1\red{1}个人;

第三个人身高为3\red{3,}右边有1\red{1}个人比他高,所以他是输入的第2\red{2}个人;第四个人身高为6\red{6,}左边有0\red{0}个人比他高,所以他是输入的第3\red{3}个人。

显然,如果排列为"6342\red{6 3 4 2}"也是满足题意的,但是字典序不是最小的。

统计

相关

在下列比赛中:

集训班18