题目描述

有 $N$ 个整数 $X_1, X_2, \\cdots, X_N$，已知 $A_i \\leq X_i \\leq B_i$。找出 $X_1, X_2, \\cdots, X_N$ 的中位数可以取得的不同值的数量。

注意事项

$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$
• 输入的所有数值均为整数。

输入

从标准输入中按以下格式输入：

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

输出

输出答案。

示例输入1

2
1 2
2 3

示例输出1

3

• 如果 $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}$。

示例输入2

3
100 100
10 10000
1 1000000000

示例输出2

9991