Problem10325--ABC354 —— C - AtCoder Magics

10325: ABC354 —— C - AtCoder Magics

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

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.

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$
```

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.

Sample 1 Input

3
2 4
1 1
3 2

Sample 1 Output

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 2 Input

5
1 1
10 2
100 3
1000 4
10000 5

Sample 2 Output

5
1 2 3 4 5
In this case, no cards can be discarded.

Sample 3 Input

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

Sample 3 Output

4
2 3 5 6

Source/Category