E - AtCoder Magics Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

高橋くんは、カードゲーム「AtCoder Magics」のカードを N 枚持っています。i 番目のカードをカード i と呼ぶことにします。各カードには強さとコストのパラメーターがあり、カード i の強さは A_i で、コストは C_i です。

高橋くんは、弱いカードは要らないので捨てることにしました。具体的には、以下の操作をできなくなるまで繰り返します。

  • 2 つのカード x, y であって、 A_x > A_y かつ C_x < C_y であるようなものを選ぶ。カード y を捨てる。

操作ができなくなったとき、捨てられなかったカードの集合は一意に定まることが証明できます。これを求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, C_i \leq 10^9
  • A_1, A_2, \dots ,A_N は全て異なる
  • C_1, C_2, \dots ,C_N は全て異なる
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

入力例 1

3
2 4
1 1
3 2

出力例 1

2
2 3

カード 1, 3 に注目すると、 A_1 < A_3 かつ C_1 > C_3 なのでカード 1 を捨てることができます。

それ以上操作をすることはできません。このときカード 2, 3 が残っているので、これらを出力します。

入力例 2

5
1 1
10 2
100 3
1000 4
10000 5

出力例 2

5
1 2 3 4 5

この場合、どのカードも捨てることができません。

入力例 3

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

出力例 3

4
2 3 5 6

Score : 350 points

Problem Statement

Takahashi has N cards from the card game "AtCoder Magics." The i-th card will be called card i. Each card has two parameters: strength and cost. Card i has a strength of A_i and a cost of C_i.

He does not like weak cards, so he will discard them. Specifically, he will repeat the following operation until it can no longer be performed:

  • Choose two cards x and y such that A_x > A_y and C_x < C_y. Discard card y.

It can be proved that the set of remaining cards when the operations can no longer be performed is uniquely determined. Find this set of cards.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, C_i \leq 10^9
  • A_1, A_2, \dots ,A_N are all distinct.
  • C_1, C_2, \dots ,C_N are all distinct.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 C_1
A_2 C_2
\vdots
A_N C_N

Output

Let there be m remaining cards, cards i_1, i_2, \dots, i_m, in ascending order. Print these in the following format:

m
i_1 i_2 \cdots i_m

Sample Input 1

3
2 4
1 1
3 2

Sample Output 1

2
2 3

Focusing on cards 1 and 3, we have A_1 < A_3 and C_1 > C_3, so card 1 can be discarded.

No further operations can be performed. At this point, cards 2 and 3 remain, so print them.

Sample Input 2

5
1 1
10 2
100 3
1000 4
10000 5

Sample Output 2

5
1 2 3 4 5

In this case, no cards can be discarded.

Sample Input 3

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

Sample Output 3

4
2 3 5 6