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 pi > pj.

Input

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

Each of the next n lines contains two integers ai and bi (1 ≤ ai, bi ≤ 109, ai ≠ bi) — 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: <image>. It has 4 inversions formed by index pairs (1, 4), (2, 3), (2, 4) and (3, 4).
import java.util.*;
import java.io.*;

public class temp {
    public static class CoordinateCompression {
        public static int N, position;
        public static int[] coordinates;

        public CoordinateCompression(int N) {
            this.N = N;
            coordinates = new int[N];
        }

        public static void add(int coordinate) {
            coordinates[position++] = coordinate;
        }

        public static void init() {
            N = position;
            for(int i = 0; i < N; i++) {
                int idx = (int)(Math.random() * i);
                int tmp = coordinates[idx];
                coordinates[idx] = coordinates[i];
                coordinates[i] = tmp;
            }

            int[] newArray = new int[N];
            for(int i = 0; i < N; i++) {
                newArray[i] = coordinates[i];
            }

            coordinates = newArray;
            Arrays.sort(coordinates);
        }

        public static int get(int key) {
            int low = 0, high = N - 1;
            while(low < high) {
                int mid = (low + high) / 2;
                if(coordinates[mid] < key) {
                    low = mid + 1;
                }
                else {
                    high = mid;
                }
            }
            return low + 1;
        }
    }

    public static class BinaryIndexedTree {
        public static int N;
        public static long[] elements;

        public BinaryIndexedTree(int N) {
            this.N = N;
            elements = new long[N + 1];
        }

        public static void addValue(int key, long value) {
            for(int i = key; i <= N; i += i & (-i)) {
                elements[i] += value;
            }
        }

        public static long sumOfElements(int key) {
            long sum = 0;
            for(int i = key; i > 0; i -= i & (-i)) {
                sum += elements[i];
            }
            return sum;
        }
    }

    public static int N;
    public static TreeMap<Integer, Integer> special = new TreeMap<Integer, Integer>();

    public static void swap(int a, int b) {
        if(!special.containsKey(a)) {
            special.put(a, a);
        }
        if(!special.containsKey(b)) {
            special.put(b, b);
        }

        int x = special.get(a);
        int y = special.get(b);
        special.put(a, y);
        special.put(b, x);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(cin.readLine());

        for(int i = 0; i < N; i++) {
            String[] s = cin.readLine().split(" ");
            swap(Integer.parseInt(s[0]), Integer.parseInt(s[1]));
        }

        BinaryIndexedTree bit = new BinaryIndexedTree(special.size() * 2);
        CoordinateCompression c = new CoordinateCompression(special.size() * 2);
        int last = 1;

        for(Map.Entry<Integer, Integer> e : special.entrySet()) {
            int first = e.getKey();
            int second = e.getValue();
            if(last != first) {
                c.add(last);
            }
            c.add(second);
            last = first + 1;
        }

        c.init();

        last = 1;
        long numInversions = 0;

        for(Map.Entry<Integer, Integer> e : special.entrySet()) {
            int first = e.getKey();
            int second = e.getValue();
            if(last != first) {
                int l = last, r = first - 1;
                long len = r - l + 1;
                numInversions += (long)len * (len - 1) / 2;
                int ll = c.get(l);
                numInversions += len * bit.sumOfElements(ll - 1);
                bit.addValue(ll, len);
            }
            int ss = c.get(second);
            numInversions += bit.sumOfElements(ss - 1);
            bit.addValue(ss, 1);
            last = first + 1;
        }
        long allPairs = last - 1;
        allPairs *= last - 2;
        allPairs /= 2;
        System.out.println(allPairs - numInversions);
    }
}
