$a_0, \dots, a_{2n}$으로 구성된 수열이 주어집니다. 처음에 모든 수는 0입니다.

$n$개의 연산이 있습니다. $i$번째 연산은 두 정수 $l_i, r_i$ ($1 \le l_i < r_i \le 2n, 1 \le i \le n$)로 표현되며, $a_{l_i}, \dots, a_{r_i-1}$에 $i$를 대입합니다. 모든 $2n$개의 정수 $l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n$은 서로 다름이 보장됩니다.

각 연산을 정확히 한 번씩, 임의의 순서로 수행해야 합니다.

모든 $n$개의 연산을 수행한 후 $a_i \neq a_{i+1}$을 만족하는 $i$ ($0 \le i < 2n$)의 개수를 최대화하고자 합니다. 그 최댓값을 출력하십시오.

입력

첫 번째 줄에는 정수 $n$ ($1 \le n \le 5 \times 10^3$)이 주어집니다.

다음 $n$개의 줄 중 $i$번째 줄에는 두 정수 $l_i, r_i$ ($1 \le l_i < r_i \le 2n$)가 주어집니다. 모든 $2n$개의 정수 $l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n$은 서로 다름이 보장됩니다.

출력

문제의 정답인 정수 하나를 한 줄에 출력하십시오.

예제

입력 1

5
2 3
6 7
1 9
5 10
4 8

출력 1

9