题目描述

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

输出格式

答えを出力せよ。

题目大意

【题目描述】

有 $N$ 个整数 $X_1, X_2, X_3,\cdots,X_N$，满足 $A_i \le X_i \le B_i$。

求 $X_1，X_2,\cdots,X_N$ 的中位数可能的不同值的数量。

【输入格式】

第一行，一个整数 $N$。
接下来 $N$ 行，每行两个整数 $A_i$，$B_i$。

【输出格式】

一行一个整数，代表可能的不同中位数取值。

Translated by

2
1 2
2 3

3

3
100 100
10 10000
1 1000000000

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$
• 入力はすべて整数である。

Sample Explanation 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}$ の $3$ つです。