Indeedなう(オープンコンテスト)

A - Table Tennis


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

Indeed 社のオフィスには卓球台がある。
n 人の社員が卓球のダブルスで試合をすることにした。
2 人ずつのペアを作ることにしたが、みんなが楽しめるようにできるだけ各ペアの強さを均等にしたいと考えている。
i 番目の人の卓球の強さは a_i で表され、ペアの強さは 2 人の強さの和で決まる。
一番強いペアと一番弱いペアの強さの差が最小になるようにペアを作ったときに、その差はいくつになるだろうか。


入力

入力は以下の形式で与えられる。

n
a_1 a_2 ... a_n
  • 1 行目には、社員の数を表す整数 n (4 \leq n \leq 100, n は偶数) が与えられる。
  • 2 行目には、社員の卓球の強さを表す整数 a_i (1 \leq a_i \leq 1{,}000) がスペース区切りで n 個与えられる。

出力

求める値を一行で出力せよ。


入力例1

4
1 3 4 10

出力例1

4

{(1,3), (4,10)}, {(1,4), (3, 10)}, {(1,10), (3,4)} の 3 通りのチーム分けが考えられる。
このうち、もっともペアの強さの差が小さいものは {(1,10), (3,4)} であり、その差は 4 である


入力例2

4
1 3 4 4

出力例2

2

Submit提出する