Maximizing Adjacent Differences in a Painted Sequence

You are given a sequence (a_0, a_1, \ldots, a_{2n}) of (2n+1) integers, initially all zero. There are (n) operations. The (i)-th operation is represented by two integers (l_i) and (r_i) (with (1 \le l_i < r_i \le 2n)). When performing the (i)-th operation, you assign the value (i) to all elements (a_{l_i}, a_{l_i+1}, \ldots, a_{r_i-1}).

All the (2n) numbers (l_1, l_2, \ldots, l_n, r_1, r_2, \ldots, r_n) are distinct. You are allowed to perform the operations in an arbitrary order (each exactly once). After all operations, let (b_i) be the final value of (a_i) for (0 \le i \le 2n). Your goal is to maximize the number of indices (i) (with (0 \le i < 2n)) such that (b_i \neq b_{i+1}).

A key observation is that no matter how you order the operations, the first and last positions (a_0) and (a_{2n}) are never painted (since every operation affects indices (\ge 1) and (\le 2n-1) respectively), so they remain 0. By appropriately choosing the order of operations, you can create many transitions between adjacent indices. It turns out that the maximum number of adjacent differences you can obtain is [ 2n - #{\text{crossing pairs}}, , ] where a pair of operations (i) and (j) (with (l_i < l_j)) is called a crossing pair if their intervals overlap without one being nested inside the other. More formally, if (l_i < l_j < r_i < r_j) then the two operations are crossing. In an optimal ordering the effect of every crossing pair is that one potential transition is lost. Thus, the answer is computed as

[ \text{Answer} = 2n - \Bigl|{ (i,j) : 1 \le i < j \le n,; l_i < l_j < r_i < r_j }\Bigr|. ]

Your task is to compute this maximum number of transitions given the intervals for the operations.

inputFormat

The first line contains a single integer (n) (the number of operations). Each of the next (n) lines contains two integers (l_i) and (r_i) representing an operation, with (1 \le l_i < r_i \le 2n). It is guaranteed that all (2n) numbers (l_1, l_2, \ldots, l_n, r_1, r_2, \ldots, r_n) are distinct.

outputFormat

Output a single integer, the maximum number of indices (i) ((0 \le i < 2n)) such that (b_i \neq b_{i+1}) can be achieved.

sample

1
1 2

2