中位数计数

题目描述

有 $N$ 个整数 $X_1, X_2, \cdots, X_N$,已知 $A_i \leq X_i \leq B_i$。 请计算 $X_1, X_2, \cdots, X_N$ 的中位数可能的取值有多少个。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。

样例

2
1 2
2 3

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}$,共 $3$ 个。

3
100 100
10 10000
1 1000000000

9991

数据范围

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

提示

$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$