Warning: Unusual memory limit!

数列 $a_0, \dots, a_{2n}$ が与えられます。最初、すべての数は $0$ です。

$n$ 回の操作があります。$i$ 番目の操作は2つの整数 $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$ はすべて相異なることが保証されています。

あなたは各操作をちょうど1回ずつ、任意の順序で行う必要があります。

すべての操作が終了した後に $a_i \neq a_{i+1}$ を満たす $i$ ($0 \le i < 2n$) の個数を最大化したいと考えています。その最大値を出力してください。

入力

1行目に整数 $n$ ($1 \le n \le 5 \times 10^3$) が与えられます。

続く $n$ 行の各行には、整数対 $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行で出力してください。

入出力例

入力 1

5
2 3
6 7
1 9
5 10
4 8

出力 1

9