문제
소로나 바이러스(COWVID-19) 때문에 격리되어 있는 농부 창호의 소들은 심심함을 달래기 위해 양자물리학을 공부하고 있다.
소들은 너무나도 심심한 나머지 실험을 거듭한 끝에 어떤 소형(小形) 입자들에 대한 새로운 정보를 알아냈는데,
발견한 자신들이 소(牛)들이고, 이 입자가 소형(小形)이기 때문에 이 입자들을 소입자라고 부르기로 하였다.
소들은 N개의 소입자를 유리 플라스크 속에 넣고 실험을 하고 있다.
소입자들은 두 정수 xi와 yi로 대표되는 특성을 가지고 있다.
소입자들은 실험용 플라스크 속 공기 중을 제멋대로 떠다니다가, 자기들끼리 부딪힌다.
부딪힌 두 소입자 pi, pj가 특성 (xi,yi), (xj,yj)를 가지고 있을 때, xi≤xj, yi≤yj를 만족한다면 그 두 소입자 중 하나는 파괴되고,
나머지 하나는 다시 공기 중을 떠다닌다.
충분한 시간이 흐른 뒤 플라스크 속에 남아 있는 소입자 개수의 최솟값을 구하는 프로그램을 작성하라.
입력
첫 줄에 소입자 개수인 N이 주어진다.(1≤N≤100,000)
다음 N 줄에 걸쳐서, 각 소입자들의 특성인 xi(-1,000,000,000≤xi≤1,000,000,000)와 yi(-1,000,000,000≤yi≤1,000,000,000)가 공백을 사이에 두고 주어진다.
모든 소입자들은 서로 다르다(다시 말해 xi=xj이고, yi=yj인 경우는 주어지지 않는다.)
출력
첫 줄에, 실험이 끝난 후 플라스크 속에 남아 있는 수 있는 소입자 개수의 최솟값을 출력한다.
예제1
4
1 0
0 1
-1 0
0 -1
1
가능한 한 가지의 시나리오는 다음과 같다.
입자 1과 입자 4가 부딪혀 입자 1이 파괴된다.
입자 2와 입자 4가 부딪혀 입자 4가 파괴된다.
입자 2와 입자 3이 부딪혀 입자 3이 파괴된다.