电子邮件

题目描述:

兔警官朱迪早年和父母一起居住在一个小村庄里。她不但在种植胡萝卜方面取得了丰硕的成果，而且在空闲时间也解决了不少编程中比较棘手的问题，并且表现的很出色。特别出众的是涉及数据结构的任务。

在一个阳光明媚的夏日，兔警官朱迪的朋友狐狸尼克给她发来了一封 $E-mail$，具体内容如下：

“我亲爱的兔警官朱迪：

希望你在忍受炎炎夏日的同时帮忙解决一个编程问题，这就是我写这封信的原因。前几天，一位朋友给了我一项艰巨的任务，我还没有办法解决。但是我知道你在这方面很在行，所以我向你寻求帮助，因为我不想在我朋友面前难堪☺。

给定一个包含 $n$个整数的数组 $a$。该数组中一个区间  $[L,R](1 \le L \lt R \le n)$ 的值定义为$max(a_L, a_{L+1},\dots , a_R) - min(a_L, a_{L+1},\dots , a_R)$。

求该数组中所有区间值的最小值。

                                                                                                                                                                   狐狸尼克留言”

由于兔警官朱迪最近工作繁忙，没有时间来解决这个难题，于是并请求聪明的你帮助她完成该任务。

输入格式:

第一行包含一个正整数$n$ ，表示数组中元素的个数。

第二行包含$n$ 个整数 $na_1,a_2,\dots, a_n$ ，第  $i( 1 \le n \le n)$个整数用$a_i$表示。

输出格式:

输出共一行一个整数，即该数组中所有区间值的最小值。

数据范围:

对于100%的数据： $ 2 \le n \le 100,000；\lvert a_i \rvert  \le 10^9$。

测试点编号	特殊限制
1~6	$2 \le n \le 100$
7~12	$2 \le n \le 2000$
13~20	无特殊限制

样例输入:

(双击复制)

样例1：
2
-2 3

样例2：
3
5 5 5

样例3：
5
1 4 1 4 1 

样例输出:

(双击复制)

样例1：
5

样例2：
0

样例3：
3

提示:

【样例3解释】

符合题意的区间之一为$[1,5]$ ，该区间的值为 $max(1,4,1,4,1) - min(1,4,1,41) = 4 - 1 = 3 $，为所有区间中值最小的。

时间限制: 1000ms
空间限制: 256MB

---

来源: 26年比赛初中组t2