あなたは小さな Kostek と一緒に積み木で塔を作っています。すでに一列に $n$ 個の塔を作っており、$i$ 番目の塔の高さは $h_i$ です。今、Kostek は自分の塔とあなたの塔の間に境界線を引きたいと考えています。境界線より左側の塔は Kostek のものになり、右側の残りの塔はあなたのものになります。2 人とも少なくとも 1 つの塔を持たなければなりません。

これから次のゲームに移るところです。そのゲームは、それぞれが自分の最も高い塔の上に斥候を置くことから始まります。斥候たちが全く異なる高さに立っているとゲームが面白くなくなってしまいます。そこで、最も公平な分け方を提案してください —— すなわち、Kostek の最も高い塔の高さとあなたの最も高い塔の高さの差の絶対値が最小になるように境界を選んでください。この最小の差を出力してください。

入力

1 行目には、塔の個数を表す整数 $n$（$2 \le n \le 300\,000$）が与えられます。

2 行目には、左から右へ並んだ各塔の高さを表す $n$ 個の整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le 10^9$）が与えられます。

出力

あなたの最も高い塔と Kostek の最も高い塔の高さの差としてあり得る最小値を表す 1 つの整数を出力してください。

入出力例

入力 1

3
200 333 100

出力 1

133

入力 2

5
5 2 4 1 5

出力 2

0

入力 3

6
5 1 4 4 2 3

出力 3

1

ノート

1 番目のテストでは、Kostek は最初の 2 つの塔の間に境界を設定すべきです。すると彼は高さ $200$ の塔を持ち、あなたは高さ $333$ と $100$ の塔を持ちます。それぞれの最も高い塔の高さは $200$ と $333$ なので、結果は $133$ となります。これより小さい差を実現することはできません。

2 番目のテストでは、どのように分けても差は $0$ になります。

3 番目のテストでは、Kostek は 1 番目、2 番目、または 3 番目の塔の後ろに境界を設定すべきです。このとき求める差は $|5 - 4| = 1$ となります。下図は、これらの最適な分け方のうちの 1 つを示しています：