Module: Méthode des lignes de balayage

Problem

Après avoir approfondi l'étude de la physique en quarantaine, les vaches ont découvert des "particules mu"
Ils expérimentent actuellement des N "particules mu" (1 ≤N ≤ 10⁵). La particule i a un "spin" décrit par deux nombres entiers x_i et y_i dans l'intervalle −10⁹…10 ⁹ inclus. Parfois deux "particules mu" interagir. Cela ne peut arriver qu'aux particules avec des spins (x_i,y_i) et (x_j,y_j ) qui ont x_i≤x_j et y_i≤y_j. Dans ces conditions, exactement une de ces particules disparaît (et rien n'arrive à l'autre). Au plus une interaction peut se produire à un moment donné.

Les vaches veulent connaître le nombre minimum de "particules mu" qui peuvent rester après une séquence arbitraire d'interactions.

Entrée
La première ligne contient un entier N, le nombre initial de "mu-particules". Chacune des N lignes suivantes contient deux entiers séparés par un espace définissant le spin de cette particule. Tous les tours sont différents.
Mentions légales
Un entier, le nombre minimum de "particules mu" qui peuvent rester après une séquence arbitraire d'interactions.

Exemples

#	Entrée	Sortie	Remarque
1	4 10 0 1 -1 0 0 -1	1	Une des séquences d'interaction possibles : Les particules 1 et 4 interagissent, la particule 1 disparaît. Les particules 2 et 4 interagissent, la particule 4 disparaît. Les particules 2 et 3 interagissent, la particule 3 disparaît. Seule la particule 2 reste.
2	3 0 0 1 1 -1 3	2	La particule 3 ne peut interagir avec aucune des autres particules, elle doit donc rester. L'une des particules 1 et 2 doit également rester.