你和年幼的 Kostek 正在用积木搭建塔。你们已经在一排建好了 $n$ 座塔，第 $i$ 座塔的高度为 $h_i$。现在 Kostek 想要在属于他的塔和属于你的塔之间划定一条边界。边界左侧的塔将归 Kostek 所有，右侧剩余的塔将归你所有。你们每个人都必须至少拥有一座塔。

你们即将开始下一个游戏，游戏开始时，你们每个人都要在自己最高的塔上放置一个侦察兵。如果侦察兵站在完全不同的高度上，游戏就会变得无趣。因此，你应该提出一个尽可能公平的划分方案——选择边界，使得 Kostek 的最高塔与你的最高塔的高度差的绝对值最小。输出这个最小的差值。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 300\,000$)，表示塔的数量。

第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$)，表示从左到右连续的塔的高度。

输出格式

输出一个整数——你的最高塔与 Kostek 的最高塔之间可能达到的最小高度差。

样例

输入样例 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

说明

在第一个样例中，Kostek 应该在头两座塔之间划定边界。这样他拥有一座高度为 200 的塔，而你拥有高度为 333 和 100 的塔。你们各自最高的塔分别是 200 和 333，因此结果为 133。不可能得到更小的差值。

在第二个样例中，任何划分方式都会导致差值为 0。

在第三个样例中，Kostek 应该在第一、第二或第三座塔之后划定边界。所需的差值即为 $|5 - 4| = 1$。下图展示了其中一种最优方案：