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.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int N =scan.nextInt();
		int[] A = new int[N];
		int[] B = new int[N];
		int num = 0;

		for (int i = 0; i < N; i++) {
			A[i] = scan.nextInt();
			B[i] = scan.nextInt();
		}

		sort(A, 0, N-1);
		sort(B, 0, N-1);

		if (N % 2 == 0) {
			num = B[N/2] + B[N/2-1] - A[N/2] - A[N/2-1] + 1;
		} else {
			num = B[(N-1)/2] - A[(N-1)/2] + 1;
		}

		System.out.println(num);
	}

	public static void sort(int[] x, int left, int right) {
		if (left >= right) {
			return;
		}

		int p = x[(left + right) / 2];
		int l = left;
		int r = right;
		int temp;

		while (l <= r) {
			while (x[l] < p) { l++; }
			while (x[r] > p) { r--; }
			if (l <= r) {
				temp = x[l];
				x[l] = x[r];
				x[r] = temp;
				l++;
				r--;
			}
		}

		sort(x, left, r);
		sort(x, l, right);
	}

}