시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB290615035.971%

문제

격자판으로 이루어진 디디몬 어드벤쳐의 어느 섬. 그 곳에는 거울냥이들이 모여 살고 있다. 거울냥이들의 생태계를 조사하던 디디는 충격적인 사실을 알게 되었다. 거울냥이들은 닿는 생명체를 전부 녹여버리는 빔을 상하좌우 네 방향으로 발사한다. 그 빔은 다른 거울냥이들을 관통하며, 어디서 발사하든 격자판의 끝에 도달한다. 거울냥이들은 동료로부터 자신의 몸을 보호하기 위해 꼬리에 거울을 달고 있도록 진화했는데, 그 거울은 항상 거울냥이의 하단 칸에 위치한다. 거울은 빔이 통과하지 않게 막으며 빔에 의해 녹지 않는다. 그리고 요즘은 무광이 대세이므로, 거울은 빔을 반사하지 않는다. 거울냥이는 죽어서 거울을 남기기 때문에 거울냥이가 녹아 없어져도 거울은 있던 자리에 그대로 남는다.

디디는 거울냥이들이 빔을 쏘는 순서가 정해져 있다는 것을 알아냈다. 하지만 이미 누군가의 빔에 의해 사라진 거울냥이는 자신의 차례가 오더라도 빔을 쏘지 못한다. 살아 있는 거울냥이들이 모두 빔을 한 번씩 순서대로 쐈을 때, 마지막까지 살아남은 거울냥이의 마릿수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 거울냥이의 마릿수를 나타내는 정수 N(1 ≤ N ≤ 2 x 105)이 주어진다.

둘째 줄부터 N개의 줄에는 빔을 쏘는 순서대로 거울냥이의 격자상의 위치 Ri, Ci(1 ≤ Ri, Ci ≤ 105)가 공백으로 구분되어 주어진다. 거울냥이와 거울냥이, 거울냥이와 거울의 위치는 중복되지 않게 주어지는 것이 보장된다.

출력

마지막까지 살아남은 거울냥이의 마릿수를 출력하시오.

예제 입력 1

3
1 1
1 4
1 3

예제 출력 1

1

예제 입력 2

2
3 2
1 2

예제 출력 2

2

출처

Contest > BOJ User Contest > 웰노운컵 > 제2회 웰노운컵 Day 2 C번