給定一個序列 $a_0, \dots, a_{2n}$，初始時所有數字皆為零。

共有 $n$ 個操作。第 $i$ 個操作由兩個整數 $l_i, r_i$ ($1 \le l_i < r_i \le 2n, 1 \le i \le n$) 表示，該操作會將 $i$ 指派給 $a_{l_i}, \dots, a_{r_i-1}$。保證所有 $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