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 Main {
static int tree[];
public static void main(String [] args)throws Exception{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int n = Integer.parseInt(br.readLine());
	StringTokenizer st;
	HashMap<Integer,Integer>map = new HashMap<Integer,Integer>();
	for(int i = 0;i < n;i++){
		st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		if(!map.containsKey(a))map.put(a,a);
		if(!map.containsKey(b))map.put(b,b);
		
		int tmp = map.get(a);
		map.put(a,map.get(b));
		map.put(b,tmp); 
	}
	ArrayList<Integer>list = new ArrayList<Integer>();
	for(Integer key : map.keySet())
		list.add(key);
	Collections.sort(list);
	tree = new int[list.size() + 1];
	long ans = 0;
	int cnt = 0;
	HashMap<Integer,Integer>compress = new HashMap<Integer,Integer>();
	for(Integer t : list){
		compress.put(t,++cnt);
		//System.out.println(cnt);
	}
	for(Integer t : list){
		int tmp = map.get(t);
		long a = Math.abs(tmp - t) - Math.abs(compress.get(t) - compress.get(tmp));
		long b = read(list.size()) - read(compress.get(tmp));
		update(compress.get(tmp),1);
		ans += (a + b);
	}
	System.out.println(ans);	
}
static int read(int a){
	int ans = 0;
	//System.out.println(a + " " + tree.length);
	while(a > 0){
		ans += tree[a];
		a -= a & (-a);
	}
	return ans;
}
static void update(int a,int val){
	while(a < tree.length){
		tree[a] += val;
		a  += a & (-a);
	}
}
}