配点 : $500$ 点

問題文

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

出力

答えを出力せよ。

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