부케

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

요약

각 튤립의 왼쪽과 오른쪽 보호 범위를 고려해, 선택한 튤립 중 어느 하나가 다른 튤립의 보호 범위에 들지 않는 가장 큰 집합의 크기를 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

세계에서 가장 큰 꽃밭 중 하나인 케우켄호프를 다녀온 리케는 꽃을 무척 좋아하게 되었습니다. 그래서 길가에 핀 튤립을 골라 아름다운 꽃다발을 만들기로 했습니다. 하지만 네덜란드의 엄격한 튤립 보호법 때문에 고를 수 있는 꽃에는 제한이 있습니다.

길을 따라 왼쪽에서 오른쪽으로 한 줄로 늘어선 $N$ 개의 튤립이 있으며, 번호는 $0$ 부터 $N-1$ 까지입니다. 보호법은 튤립 $i$ 마다 두 정수 $l_i$ 와 $r_i$ 를 정합니다. 리케가 튤립 $i$ 를 고르면, 바로 왼쪽의 $l_i$ 개 튤립과 바로 오른쪽의 $r_i$ 개 튤립은 꽃다발에 넣을 수 없습니다. 왼쪽에 튤립이 $l_i$ 개보다 적거나 오른쪽에 $r_i$ 개보다 적으면, 그쪽의 튤립은 모두 제외됩니다.

보호법을 지키면서 리케가 고를 수 있는 튤립의 최대 개수를 구하세요.

입력

첫 줄에 튤립의 개수 $N$ 이 주어집니다.

이어지는 $N$ 개의 줄 중 $i$ 번째 줄에는 두 정수 $l_i$ 와 $r_i$ 가 주어집니다.

출력

리케가 고를 수 있는 튤립의 최대 개수를 한 줄에 출력합니다.

제한

$1 \leq N \leq 2 \cdot 10^5$ .
$0 \leq l_i, r_i \leq N$ for $i = 0,1,\ldots, N-1$ .

힌트

첫 번째 예제에서 리케가 튤립 $0$ 을 고르면 오른쪽의 두 튤립은 고를 수 없습니다. 튤립 $1$ 을 고르는 것은 튤립 $2$ 를 고르는 데 방해가 되지 않지만, 튤립 $2$ 를 고르면 튤립 $1$ 을 고를 수 없습니다. 따라서 두 튤립을 함께 고를 수 없고, 최대값은 $1$ 입니다.

두 번째 예제에서 최대값은 $3$ 입니다. 이를 얻는 방법은 아래 그림과 같습니다. 다른 방법으로는 더 작은 값만 얻을 수 있습니다.

예제5

예제 1
입력
```
3
0 3
1 0
1 0
```
예상 출력
```
1
```
예제 2
입력
```
5
0 3
1 0
0 1
2 0
1 0
```
예상 출력
```
3
```
예제 3
입력
```
7
0 0
0 0
1 0
1 0
2 0
3 0
2 0
```
예상 출력
```
4
```
예제 4
입력
```
6
2 2
2 2
2 2
2 2
2 2
2 2
```
예상 출력
```
2
```
예제 5
입력
```
7
0 2
2 0
1 1
2 2
0 0
0 1
0 1
```
예상 출력
```
3
```