Wesleyはイースターのために $N$ 個の要素からなる配列 $(a_1, a_2, \dots, a_N)$ を手に入れ、それをソートしたいと考えている（つまり、$a_1 \le a_2 \le \dots \le a_N$ となるようにしたい）。

退屈したWesleyは、自分自身に制限を課すことにした。2つの要素の絶対値の差が $K$ 以下である場合にのみ、それらを入れ替えることができるというルールである。要素は配列内のどこにあってもよく、絶対値の差が $K$ 以下であれば、Wesleyはそれらを入れ替えることができる。

残念なことに、Wesleyはすぐに、配列をソートすることが不可能かもしれないと気づいた。そこで彼は、配列をソートするために必要な $K$ の最小値はいくらかという疑問を抱いた。

入力

1行目には、配列の要素数 $N$ が与えられる ($1 \le N \le 2 \cdot 10^5$)。

2行目には、配列の各要素 $a_1, a_2, \dots, a_N$ が与えられる ($1 \le a_i \le 10^{18}$)。

出力

配列をソートするために必要な $K$ の最小値を出力せよ。もし要素がすでにソートされている場合は、0を出力すること。

入出力例

入力 1

8
1 4 4 2 7 14 12 10

出力 1

2