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.io.IOException;
import java.util.InputMismatchException;
import java.util.TreeSet;
import java.util.HashMap;
import java.util.ArrayList;

public class InfiniteInversions {
    public static void main(String[] args) {
        FasterScanner sc = new FasterScanner();
        
        int N = sc.nextInt();
        
        int[] A = new int[N];
        int[] B = new int[N];
        TreeSet<Integer> used = new TreeSet<Integer>();
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
            B[i] = sc.nextInt();
            used.add(A[i]);
            used.add(B[i]);
        }
        
        int idx = 1;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> bak = new HashMap<Integer, Integer>();
        for (int num : used) {
            map.put(num, idx);
            bak.put(idx, num);
            idx++;
        }
        
        Integer[] arr = new Integer[200002];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }
        
        for (int i = 0; i < N; i++) {
            int idxA = map.get(A[i]);
            int idxB = map.get(B[i]);
            int tmp = arr[idxA];
            arr[idxA] = arr[idxB];
            arr[idxB] = tmp;
        }
        
        long baseCount = Inversion.count(arr);
        
        ArrayList<Gap> gaps = new ArrayList<Gap>();
        gaps.add(new Gap(0, 0, 0));
        for (int i = 1; i < idx - 1; i++) {
            if (bak.get(i + 1) - bak.get(i) > 1) {
                Gap g = new Gap(bak.get(i) + 1, bak.get(i + 1) - 1, bak.get(i + 1));
                gaps.add(g);
            }
        }
        gaps.add(new Gap(1000000007, 1000000009, 1000000000));
        
        int[] partial = new int[gaps.size()];
        partial[0] = gaps.get(0).size();
        for (int i = 1; i < gaps.size(); i++) {
            partial[i] = partial[i-1] + gaps.get(i).size();
        }
        
        for (int i = 1; i < idx; i++) {
            int a, b;
            if (bak.get(arr[i]) > bak.get(i)) {
                b = bak.get(arr[i]);
                a = bak.get(i);
            } else {
                b = bak.get(i);
                a = bak.get(arr[i]);
            }

            int L = 0, R = gaps.size() - 1;
            
            while (L <= R) {
                int M = (L + R) / 2;
                if (R - L == 1) {
                    break;
                }
                if (gaps.get(M).end < b) L = M;
                else R = M;
            }
            int Lb = L;
            
            L = 0;
            R = gaps.size() - 1;
            while (L <= R) {
                int M = (L + R) / 2;
                if (R - L == 1) break;
                else if (gaps.get(M).end < a) L = M;
                else R = M;
            }
            int La = L;
            baseCount += partial[Lb] - partial[La];
        }
        
        System.out.println(baseCount);
    }
    
    public static class Gap {
        public int start, end, pos;
        
        public Gap(int s, int e, int p) {
            this.start = s;
            this.end = e;
            this.pos = p;
        }
        
        public int size() {
            return this.end - this.start + 1;
        }
    }
    
    public static class Inversion {
        // merge and count
        private static long merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
            long inversions = 0;

            // copy to aux[]
            for (int k = lo; k <= hi; k++) {
                aux[k] = a[k]; 
            }

            // merge back to a[]
            int i = lo, j = mid+1;
            for (int k = lo; k <= hi; k++) {
                if      (i > mid)                a[k] = aux[j++];
                else if (j > hi)                 a[k] = aux[i++];
                else if (less(aux[j], aux[i])) { a[k] = aux[j++]; inversions += (mid - i + 1); }
                else                             a[k] = aux[i++];
            }
            return inversions;
        }

        // return the number of inversions in the subarray b[lo..hi]
        // side effect b[lo..hi] is rearranged in ascending order
        private static long count(Comparable[] a, Comparable[] b, Comparable[] aux, int lo, int hi) {
            long inversions = 0;
            if (hi <= lo) return 0;
            int mid = lo + (hi - lo) / 2;
            inversions += count(a, b, aux, lo, mid);  
            inversions += count(a, b, aux, mid+1, hi);
            inversions += merge(b, aux, lo, mid, hi);
            assert inversions == brute(a, lo, hi);
            return inversions;
        }


        // count number of inversions in the array a[] - do not overwrite a[]
        public static long count(Comparable[] a) {
            Comparable[] b   = new Comparable[a.length];
            Comparable[] aux = new Comparable[a.length];
            for (int i = 0; i < a.length; i++) b[i] = a[i];
            long inversions = count(a, b, aux, 0, a.length - 1);
            return inversions;
        }


        // is v < w ?
        private static boolean less(Comparable v, Comparable w) {
            return (v.compareTo(w) < 0);
        }

        // count number of inversions in a[lo..hi] via brute force (for debugging only)
        private static long brute(Comparable[] a, int lo, int hi) {
            long inversions = 0;
            for (int i = lo; i <= hi; i++)
                for (int j = i + 1; j <= hi; j++)
                    if (less(a[j], a[i])) inversions++;
            return inversions;
        }


        // count number of inversions via brute force
        public static long brute(Comparable[] a) {
            return brute(a, 0, a.length - 1);
        }
    }
    
    public static class FasterScanner {
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = System.in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
            
        public int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }
        
        public long[] nextLongArray(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }
}