题目描述

萌萌哒$\red{Salroey}$最近在研究数列，研究数列当然就要观察数列的特征。

于是对于一个长度为$\red{m}$的序列$\red{S_i }$(下标从$\red{1}$开始)，$\red{Salroey}$定义它的特征值为:

$\red{max\{ min \{|S_i- S_j|\},m\}}$ $\red{（1<=i<j<=m）}$

即序列中任意两个不同元素差的绝对值的最小值与区间长度的较大值，两个元素不同当 且仅当下标不同。

$\red{Salroey}$想得到一个特征值较小的序列，不过在随机生成了很多序列之后$\red{Salroey}$发现它们 的特征值都很大，于是她设计了一种办法来找特征值较小的序列。

给定一个长度为$\red{n}$的序列，找出他特征值最小的连续子序列，输出这个连续子序列的权值 即可。

注意:选择的连续子序列长度必须至少为$\red{2，}$给定的序列不一定是随机的。

输入格式

第一行一个正整数$\red{n，}$表示序列的产长度。

第二行$\red{n}$个正整数$\red{a_i，}$表示给定的序列。

输出格式

输出一行一个整数表示连续子序列特征值的最小值。

样例

输入样例

5 
9 20 15 6 10

输出样例

4

提示

对于$\red{30\%}$的数据，$\red{n≤}$$\red{1000}$

对于$\red{60\%}$的数据，$\red{n≤}$$\red{10^5}$

对于$\red{100\%}$的数据，$\red{2≤}$$\red{n≤}$$\red{10^6}$;$\red{1≤}$$\red{a_i≤}$$\red{10^9}$

样例解释

对于样例$\red{1，}$选取区间$\red{[4, 5]}$即可。