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 cnt = Inversion.count(arr);
        
        ArrayList<Gap> gaps = new ArrayList<Gap>();
        gaps.add(new Gap(0, -1));
        for (int i = 1; i < idx - 1; i++) {
        	int next = bak.get(i + 1);
        	int curr = bak.get(i);
        	if (next - curr > 1) {
        		Gap g = new Gap(curr + 1, next - 1);
        		gaps.add(g);
        	}
        }
        gaps.add(new Gap(1000000007, 1000000006));
        
        long[] psums = new long[gaps.size() + 1];
        for (int i = 0; i < gaps.size(); i++) {
        	psums[i + 1] = psums[i] + gaps.get(i).size();
        }
        
        for (int i = 1; i < idx; i++) {
        	int origNum = bak.get(arr[i]);
        	int origIdx = bak.get(i);
        	int lb = Math.min(origNum, origIdx);
        	int rb = Math.max(origNum, origIdx);
        	
        	int L, R, good;
        	
        	L = 0;
        	R = gaps.size() - 1;
        	good = R;
        	while (L <= R) {
        		int M = (L + R) / 2;
        		if (gaps.get(M).start > lb) {
        			good = M;
        			R = M - 1;
        		} else {
        			L = M + 1;
        		}
        	}
        	int loIdx = good;
        	
        	L = 0;
        	R = gaps.size() - 1;
        	good = L;
        	while (L <= R) {
        		int M = (L + R) / 2;
        		if (gaps.get(M).start < rb) {
        			good = M;
        			L = M + 1;
        		} else {
        			R = M - 1;
        		}
        	}
        	int hiIdx = good;
        	
        	long add = Math.max(0, psums[hiIdx + 1] - psums[loIdx]);
        	cnt += add;
        }
        
        System.out.println(cnt);
    }
    
    public static class Gap {
    	public int start, end;
    	
    	public Gap(int s, int e) {
    		this.start = s;
    		this.end = e;
    	}
    	
    	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;
		}
	}
}