AtCoder 魔法卡

题目描述

高桥君有「AtCoder 魔法卡」卡牌游戏中的 $N$ 张卡。第 $i$ 张卡称为卡 $i$。每张卡都有两个参数:强度与费用。卡 $i$ 的强度为 $A_i$,费用为 $C_i$。

他不喜欢弱小的卡,所以会丢弃它们。具体来说,他会反复执行以下操作,直到无法再进行为止:

选出两张卡 $x$ 和 $y$,使得 $A_x \gt A_y$ 且 $C_x \lt C_y$,然后丢弃卡 $y$。

可以证明,当操作无法再进行时剩下的卡集合是唯一确定的。求出这个卡集合。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $C_1$
$A_2$ $C_2$
$\vdots$
$A_N$ $C_N$

输出格式

设剩下的卡有 $m$ 张,按编号升序为 $i_1, i_2, \dots, i_m$。按以下格式输出:

$m$
$i_1$ $i_2$ $\cdots$ $i_m$

样例

3
2 4
1 1
3 2

2
2 3

关注卡 $1$ 和卡 $3$,有 $A_1 \lt A_3$ 且 $C_1 \gt C_3$,所以可以丢弃卡 $1$。

之后无法再进行任何操作。此时剩下卡 $2$ 和卡 $3$,输出它们。

5
1 1
10 2
100 3
1000 4
10000 5

5
1 2 3 4 5

这种情况下,任何卡都不能被丢弃。

6
32 101
65 78
2 29
46 55
103 130
52 40

4
2 3 5 6

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le A_i, C_i \le 10^9$
• $A_1, A_2, \dots, A_N$ 互不相同
• $C_1, C_2, \dots, C_N$ 互不相同
• 所有输入值均为整数