P6283 [USACO20OPEN] The Moo Particle S

FJ’s cows have been bored lately, so they came up with a brand-new way to kill time: studying advanced physics. In fact, they even managed to discover a new subatomic particle, which they named the “Moo Particle”. The cows are running an experiment involving $N$ Moo Particles ($1\le N\le 10^5$). The “spin” of particle $i$ can be described by two integers $x_i$ and $y_i$ in the range $-10^9\ldots 10^9$. Sometimes two Moo Particles interact. Two particles with spins $(x_i,y_i)$ and $(x_j,y_j)$ will interact if and only if $x_i\le x_j$ and $y_i\le y_j$. Under these conditions, it is possible for one of the two particles to disappear (the other particle does not change). At any given moment, at most one interaction can happen. The cows want to know the minimum number of Moo Particles that can remain after performing some sequence of interactions.

The first line contains an integer $N$, the initial number of Moo Particles. The next $N$ lines each contain two space-separated integers, representing the spin of one particle. All particle spins are distinct.

Output one integer, the minimum number of Moo Particles that can remain after performing some sequence of interactions.

### Explanation for Sample Input/Output 1 One possible sequence of interactions: - Particle $1$ interacts with particle $4$, and particle $1$ disappears. - Particle $2$ interacts with particle $4$, and particle $4$ disappears. - Particle $2$ interacts with particle $3$, and particle $3$ disappears. Only particle $2$ remains. ### Explanation for Sample Input/Output 2 Particle $3$ cannot interact with any other particle, so it must remain. Among particles $1$ and $2$, at least one must remain. ### Subtasks - Test cases $3$-$6$ satisfy $N\le 10^3$. - Test cases $7$-$12$ have no additional constraints. Translated by ChatGPT 5