問題文

NN 個の整数 A1,A2,,ANA_1,A_2,…,A_N が与えられます。ただし、 NN は偶数です。

あなたは、好きな実数を 11 つ選んでこの整数の組に加えることができます。 この時、 N+1N+1 個の数について、平均値と中央値が等しくなるような実数の選び方は何通りありますか。

ただし、平均値とは N+1N+1 個の数すべての和を N+1N+1 で割って得られる実数、 中央値とは N+1N+1 (奇数)個の数のうち N/2+1N/2+1 番目に小さい数のことです。

制約

  • 2N2×1052\leq N\leq 2\times 10^5
  • NNは偶数である
  • 1Ai1091\leq A_i\leq 10^9
  • 入力は全て整数である

入力

N
A_1 A_2 ... A_N

出力

与えられた条件を満たす選び方の数を出力してください。

サンプル

入力1
2
1 2
出力1
3

0,1.5,30,1.5,3 を選ぶと条件を満たすようにできます。 ここで、与えられる数は全て整数ですが、選ぶことの出来る数は整数に限られないことに注意してください。 同様に、与えられる数は正ですが、 00 や負の数を選んでも構いません。

入力2
4
1 1 1 1
出力2
1

11 を選ぶしかありません。

入力3
28
730 793 1028 1129 1373 1580 1246 1256 1712 1910 1281 2020 2269 2221 2105 2262 1561 2558 2074 2018 2216 1745 2198 2034 2796 2304 2576 1561
出力3
1

提出


Go (1.21)