在 Đakovo 旁的一个小村庄里住着 Kasap。虽然农业是他的本行、热爱与归宿，但在空闲时间，Kasap 会解决一些算法竞赛的题目，并且做得非常好。他对涉及数据结构的任务特别感兴趣。

在一个阳光明媚的夏日，Kasap 的朋友 Mirko 给他寄来了一封信，我们将其完整转录如下：

“亲爱的 Kasap：

希望你能安度这些炎热的夏日。我写这封信是因为我遇到了一个问题。 前几天一个朋友给了我一个很难的任务，我至今还没能解决。既然我知道你喜欢这类任务，我想向你寻求帮助，因为我不想在朋友面前丢脸。 题目中有一个由 $N$ 个整数组成的数组 $A$。你需要找到一个值最小的区间。区间 $[L, R]$ 的值定义为该区间内数字的最大值与最小值之差：$\max(A[L], A[L+1], \dots, A[R]) - \min(A[L], A[L+1], \dots, A[R])$。提醒一下，我们只考虑 $L$ 严格小于 $R$ 的区间。 谢谢你， Mirko”

经过一周的苦思冥想，Kasap 仍然没能解决这个问题，于是请求你来帮助他。

输入格式

输入的第一行包含一个正整数 $N$（$2 \le N \le 100\,000$）。

输入的第二行包含 $N$ 个整数，其绝对值小于 $10^9$。

输出格式

输出一个区间的最小可能值。

子任务

• 在价值 $20$ 分的测试数据中，满足 $N \le 100$。
• 在价值 $40$ 分的测试数据中，满足 $N \le 2\,000$。

样例

输入样例 1

2
1 3

输出样例 1

2

输入样例 2

3
1 1 1

输出样例 2

0

输入样例 3

5
1 2 1 2 1

输出样例 3

1

说明

样例 3 解释： 区间 $[1, 5]$ 的最大值为 $2$，而同一区间上的最小值为 $1$，因此该区间的值为 $2 - 1 = 1$，这也是所有区间中可能达到的最小值。