Дана последовательность $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$ различны.

Вам необходимо выполнить каждую операцию ровно один раз в произвольном порядке.

Вы хотите максимизировать количество таких $i$ ($0 \le i < 2n$), что $a_i \neq a_{i+1}$ после выполнения всех $n$ операций. Выведите это максимальное число.

Входные данные

Первая строка содержит целое число $n$ ($1 \le n \le 5 \times 10^3$).

$i$-я строка из следующих $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

5
2 3
6 7
1 9
5 10
4 8

Выходные данные 1

9