問題文

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

入力例 2

3
100 100
10 10000
1 1000000000

出力例 2

9991