004 - 集会所

問題文

イヅア村の住民は村に集会所を建てることにしました。この村では東西に一直線に伸びる道路に沿って建物を建てられる地点が決まっています。最も西の地点を０番目の地点として、そこから等間隔に東に向かって１番目、２番目、…と地点番号が与えられています。村人の家と集会所を建てることができるのは、これらの地点だけです。各家には１人以上の村人が住んでいます。どの村人も隣の地点まで１分間で移動できます。 集会を開くのに便利なように、ある時刻に一斉に全ての村人が自分の家から集会所に向かったとき、全員が集まるのに必要な時間が最小になるような場所に、集会所を建てることにしました。 家の建っている地点の番号が与えられたときに、全ての村人が集会所に集まるのに必要な時間の最小値を計算するプログラムを作成せよ。ただし、集会所の地点番号が家の地点番号と重複してもよいものとする。

入出力

入力

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

$N$
$x$1 $x$2 ... $x$$N$

１行に数値$N$(2 ≤ $N$ ≤ 1000)が与えられる。２行目に家の建っている地点番号x_i (0 ≤ $x$_$i$ ≤ 2000)が与えられる。ただし、家の地点番号は全て異なる($i$ ≠ $j$ について $x$_$i$ ≠ $x$_$j$である)。

出力

集会所に集まるのに必要な最小の時間を分単位で１行に出力する。

入出力例

入力例1

3
4 0 1

出力例1

2

入力例2

2
1 2

出力例2

1