题目描述

给定一个长度为 $n$ 的整数数列 $a_1,a_2,\ldots,a_n$，求它所有长度不小于 $2$ 的连续子区间中，最大值与最小值之差的最小值。

输入格式

从文件 interval.in 中读取数据。

第一行输入一个整数 $n$。

接下来一行包含 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

将结果输出到文件 interval.out 中。

输出一个整数，表示答案。

样例

2
1 3

2

3
1 1 1

0

5
1 2 1 2 1

1

数据范围与提示

对于样例 $3$，区间 $[1,5]$ 的最大值是 $2$，最小值是 $1$，此时差值为 $2-1=1$，可以证明这是最小的差值。

对于 $20\%$ 的数据，$n\le 100$；

对于 $40\%$ 的数据，$n\le 1000$；

对于 $60\%$ 的数据，$n\le 10^5$；

对于 $80\%$ 的数据，$n\le 10^6$；

对于 $100\%$ 的数据，$2\le n\le 10^7$，$0\le a_i\le 10^9$，且 $a_i$ 为整数。