Mika 正在和她的朋友们玩 The Mind（心灵同步）游戏。

游戏使用卡牌进行，每张卡牌上写有一个整数。所有卡牌上的数值都是互不相同的。玩家们不断出牌，在桌面上叠成一叠。初始时，牌堆中只有一张写有数字 0 的卡牌。每个玩家都会分到一张数值在 $1$ 到 $10^9$ 之间的卡牌。然后玩家们开始以任意顺序出牌。当一个玩家出牌时，他们会将牌放在牌堆的最上方。游戏的目标是让所有玩家都出完牌，且牌堆中的卡牌数值从底到顶单调递增。如果有任何玩家没有出牌，或者牌堆没有保持递增，玩家们就输了；否则，他们获胜。卡牌分发后，玩家之间不允许进行任何交流。

Mika 和她的朋友们想出了一个策略。他们在游戏开始前约定一个整数 $d$。在游戏过程中，如果某个玩家手牌的数值为 $x$，且牌堆顶部的数值为 $y$，满足 $x - y \le d$，那么该玩家就会出牌。如果 $x - y > d$，该玩家就不会出牌。如果有多名玩家同时出牌，这些卡牌可能会以任意顺序放置在牌堆顶部，且这个顺序不受玩家控制。

现在给定将要分发给玩家们的卡牌数值。你的任务是找到一个整数 $d$，使得玩家们使用该策略时能够保证获胜。

输入格式

第一行包含一个整数 $n$ — 玩 The Mind 游戏的玩家人数（$3 \le n \le 100\,000$）。

第二行包含 $n$ 个整数 — 分发给玩家们的卡牌数值。

所有给定的卡牌数值都是互不相同的正整数，且不超过 $10^9$。

输出格式

输出一个整数 $d$，表示 Mika 和她的朋友们为了保证使用该策略获胜应该使用的参数。如果不存在这样的 $d$，输出 0。如果存在多个满足条件的 $d$，输出其中任意一个。

样例

输入样例 1

5
5 13 2 10 8

输出样例 1

4

输入样例 2

5
4 13 2 8 7

输出样例 2

0

说明

在第一个样例中，$d = 3$ 也是一个正确的答案。