출입 기록

면접 대비

시간 제한1초메모리 제한1024 MB

요약

부대에 아무도 없는 상태에서 시작해 같은 상태로 끝나야 한다는 조건에서, 시간순 출입 기록이 모순 없이 이어지도록 빠진 기록의 최소 개수를 구한다.

난이도: 보통10점 중 4점
유형: 구현, 그리디
정답자: 아직 제출이 없습니다

문제

위병소에서 근무하는 헌병은 오늘 근무를 끝마치고 보안 점검을 위해 출입 기록을 살펴보던 중, 오늘 출입 기록의 일부가 누락되었다는 사실을 깨달았다!

오늘 기록된 출입 기록은 총 $N$ 개이며, 출입 기록은 반드시 출입자가 출입한 시간순으로 기록된다.

$i$ 번째 출입 기록은 두 개의 정수 $a\_i, b\_i$ 로 기록되는데, $a\_i$ 는 출입하는 사람의 번호를 의미하며, $b\_i$ 가 $1$ 이면 부대로 들어갔다는 뜻이고 $b\_i$ 가 $0$ 이면 부대에서 나왔다는 뜻이다. 또한, 출입 기록을 시작하기 전과 출입 기록을 끝낸 후에는 부대 내에 아무도 없었다고 한다.

오늘의 출입 기록을 토대로 오늘 하루동안 누락된 출입 기록의 최소 개수를 구하여라.

입력

첫 번째 줄에 출입 기록의 개수 $N$ 이 주어진다. $(1\leq N\leq 200\\,000)$

두 번째 줄부터 $N+1$ 번째 줄까지, $i$ 번째 출입 기록을 나타내는 정수 $a\_i$ 와 $b\_i$ 가 공백으로 구분되어 주어진다. $(1\leq a\_i\leq 200\\,000;$ $0\leq b\_i\leq 1)$

출력

오늘 하루 동안 누락된 출입 기록의 최소 개수를 출력한다.

예제2

예제 1
입력
```
8
1 1
2 1
1 1
4 1
3 0
5 1
4 0
1 0
```
예상 출력
```
4
```
예제 2
입력
```
4
100 1
345 1
345 0
100 0
```
예상 출력
```
0
```