There is an infinite sequence consisting of all positive integers in the increasing order: p = {1, 2, 3, ...}. We performed n swap operations with this sequence. A swap(a, b) is an operation of swapping the elements of the sequence on positions a and b. Your task is to find the number of inversions in the resulting sequence, i.e. the number of such index pairs (i, j), that i < j and p_{i} > p_{j}.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of swap operations applied to the sequence.

Each of the next n lines contains two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ 10^9, a_{i} ≠ b_{i}) — the arguments of the swap operation.


-----Output-----

Print a single integer — the number of inversions in the resulting sequence.


-----Examples-----
Input
2
4 2
1 4

Output
4

Input
3
1 6
3 4
2 5

Output
15



-----Note-----

In the first sample the sequence is being modified as follows: $\{1,2,3,4,5, \ldots \} \rightarrow \{1,4,3,2,5, \ldots \} \rightarrow \{2,4,3,1,5 \ldots \}$. It has 4 inversions formed by index pairs (1, 4), (2, 3), (2, 4) and (3, 4).

Difficulty: interview

Starter code:

Solutions:
import sys
from collections import defaultdict
 
class BIT():
    def __init__(self, n):
        self.n = n
        self.tree = [0] * n
    
    def _get_sum(self, r):
        '''
        sum on interval [0, r)
        '''
        result = 0
        while r > 0:
            result += self.tree[r-1]
            r &= (r - 1)
        return result
    
    def get_sum(self, l, r):
        '''
        sum on interval [l, r)
        '''
        return self._get_sum(r) - self._get_sum(l)
    
    def add(self, i, value=1):
        while i < self.n:
            self.tree[i] += value
            i |= (i + 1)

reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__

n = int(input())
swaps = []
for _ in range(n):
    i, j = list(map(int, input().split()))
    swaps.append(i)
    swaps.append(j)

pos = defaultdict(list)
for i, val in enumerate(swaps):
    pos[val].append(i)

c = 0
prev = -1
compr = [0] * (2*n)
decompr = {}
for val in sorted(swaps):
    if prev == val: continue
    for j in pos[val]:
        compr[j] = c
    decompr[c] = val
    c += 1
    prev = val

arr = list(range(c))
for t in range(n):
    i, j = compr[t<<1], compr[t<<1|1]
    arr[i], arr[j] = arr[j], arr[i]

bit = BIT(c)
total_inv = 0
for i, val in enumerate(arr):
    total_inv += bit.get_sum(val+1, c)
    if i != val:
        total_inv += abs(decompr[val] - decompr[i]) - abs(val - i)
    bit.add(val)
print(total_inv)