题目描述

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.

B_i$。求$X_1, X_2, \cdots, X_N$ 的中位数可以取多少个不同的值。

输入格式

输入内容按以下格式标准输入：

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$:$
$A_N$ $B_N$

输出格式

打印答案。

样例 #1

样例输入 #1

2
1 2
2 3

样例输出 #1

3

样例 #2

样例输入 #2

3
100 100
10 10000
1 1000000000

样例输出 #2

9991

说明

$X_1, X_2, \cdots, X_N$ 的中位数定义如下。设 $x_1, x_2, \cdots, x_N$ 是将 $X_1, X_2, \cdots, X_N$ 按升序排序的结果。

• 如果 $N$ 是奇数，则中位数为 $x_{(N+1)/2}$ ；
• 如果 $N$ 是偶数，则中位数是 $(x_{N/2} + x_{N/2+1}) / 2$ 。

数据规模与约定

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq B_i \leq 10^9$
• 所有输入值均为整数。

样例 $1$ 解释

• 如果 $X_1 = 1$ 和 $X_2 = 2$ ，则中位数为 $\frac{3}{2}$ ；

• 如果 $X_1 = 1$ 和 $X_2 = 3$ ，中位数为 $2$ ；

• 如果 $X_1 = 2$ 和 $X_2 = 2$ ，中位数为 $2$ ；

• 如果 $X_1 = 2$ 和 $X_2 = 3$ ，中位数为 $\frac{5}{2}$ 。

因此，中位数可以有三个值： $\frac{3}{2}$ 、 $2$ 和 $\frac{5}{2}$ 。