Bạn được cho một dãy số $a_0, \dots, a_{2n}$. Ban đầu, tất cả các số đều bằng 0.

Có $n$ thao tác. Thao tác thứ $i$ được biểu diễn bởi hai số nguyên $l_i, r_i$ ($1 \le l_i < r_i \le 2n, 1 \le i \le n$), gán giá trị $i$ cho $a_{l_i}, \dots, a_{r_i-1}$. Đảm bảo rằng tất cả $2n$ số nguyên $l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n$ đều phân biệt.

Bạn cần thực hiện mỗi thao tác đúng một lần, theo thứ tự tùy ý.

Bạn muốn tối đa hóa số lượng $i$ ($0 \le i < 2n$) sao cho $a_i \neq a_{i+1}$ sau khi thực hiện tất cả $n$ thao tác. Hãy in ra số lượng tối đa đó.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 5 \times 10^3$).

Dòng thứ $i$ trong $n$ dòng tiếp theo chứa một cặp số nguyên $l_i, r_i$ ($1 \le l_i < r_i \le 2n$). Đảm bảo rằng tất cả $2n$ số nguyên $l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n$ đều phân biệt.

Dữ liệu ra

In ra một số nguyên duy nhất là kết quả trên một dòng.

Ví dụ

Dữ liệu vào 1

5
2 3
6 7
1 9
5 10
4 8

Dữ liệu ra 1

9