你手上有 N 张魔法卡牌,编号 1 \sim N。第 i 张卡牌的**强度**为 A_i,**费用**为 C_i。强度越大表示越强,费用越小表示越划算。
如果存在另一张卡牌 y 满足
A_y > A_x \quad \text{且} \quad C_y < C_x
(即 y 比 x **既强又便宜**),就称卡牌 x 是**多余**的,多余的卡牌会被丢弃。
请你反复丢弃所有多余的卡牌,直到没有卡牌可以再被丢弃为止,问最后剩下哪些卡牌。
> 说明:本题保证任意两张卡牌的 A 互不相同、C 也互不相同,所以"既强又便宜"里不需要考虑并列的情况。
N
A_1 C_1
A_2 C_2
...
A_N C_N
第一行一个整数,表示最后剩下的卡牌张数 m。
第二行 m 个整数,按**编号升序**输出这些卡牌的编号,用空格分隔,行末换行。
3 2 4 1 1 3 2
2 2 3
5 1 1 10 2 100 3 1000 4 10000 5
5 1 2 3 4 5
- 2 \le N \le 2\times 10^5
- 1 \le A_i \le 10^9,1 \le C_i \le 10^9,且保证所有 A_i 两两不同、所有 C_i 两两不同
样例1说明:卡牌 1(强度 2、费用 4)被卡牌 3(强度 3、费用 2)碾压,丢弃。卡牌 2(强度 1、费用 1)没有更便宜的了,保留。卡牌 3 最强,保留。最后剩下编号 2 和 3。
| t1 | 10 | 2 \le N \le 10,A_i, C_i \le 50 |
| t2 | 20 | N \le 300 |
| t3 | 30 | N \le 5000 |
| t4 | 40 | N \le 2\times 10^5;
| 时间限制 | 1 秒 |
| 内存限制 | 128 MB |