There are N integers X_1, X_2, \cdots, X_N, and we know that A_i \leq X_i \leq B_i. Find the number of different values that the median of X_1, X_2, \cdots, X_N can take.

Constraints

* 2 \leq N \leq 2 \times 10^5
* 1 \leq A_i \leq B_i \leq 10^9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 B_1
A_2 B_2
:
A_N B_N


Output

Print the answer.

Examples

Input

2
1 2
2 3


Output

3


Input

3
100 100
10 10000
1 1000000000


Output

9991
	import java.util.*;
	import java.util.Map.Entry;
	 
	 
	 class Main {
		 static int mod =  (int) (Math.pow(10,9)+7);
//		 static int mod =  (int) 998244353;
		 public static void main(String[] args) {
	    	
	        Scanner sc = new Scanner(System.in);

	        
	        int N = sc.nextInt();
	        Integer[][] a = new Integer[N][3];
	        Integer[][] b = new Integer[N][3];
	        for(int i=0;i<N;i++) {
	        	a[i][0] = Integer.parseInt(sc.next());
	        	a[i][1] = Integer.parseInt(sc.next());
	        	a[i][2] = i;
	        	b[i][0] = a[i][0];
	        	b[i][1] = a[i][1];
	        	b[i][2] = a[i][2];
	        }
	        Arrays.sort(a, (d, c) -> Integer.compare(d[0], c[0]));
	        Arrays.sort(b, (d, c) -> Integer.compare(c[1], d[1]));
	        long ans=0;
	        if(N%2==1) {
	        	Integer min = a[N/2][0];
	        	Integer max = b[N/2][1];
        		Integer r = 0;
        		ans=max-min+1;
	        	for(int i=0;i<N;i++) {
	        		if(r>=max)break;
	        		if(r<a[i][0]&&min<a[i][0]) {
	        			ans=ans-(Math.min(a[i][0], max)-Math.max(r, min)-1);
	        		}
	        		r=Math.max(r, a[i][1]);
	        	}
	        	
	        } else {
	        	Integer min = a[N/2-1][0]+a[N/2][0];
	        	Integer max = b[N/2-1][1]+b[N/2][1];
        		ans=(max-min+1);
	        	
	        }
	        
	        System.out.println(ans);
	    }
	}