时间限制：1秒　　内存限制：256M

---

题目描述

给定一个包含 \(N\) 个整数的数组 \(A\)。

该数组中一个区间 \([L,R]\) （\(L \lt R\)）的值定义为 \(\max(A[L],A[L+1],\cdots,A[R])-\min(A[L],A[L+1],\cdots,A[R])\)。

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

输入格式

第一行输入正整数 \(N\)。

第二行输入 \(N\) 个整数 \(A_i\)，表示数组中的数。

输出格式

输出所有区间值的最小值。

输入输出样例 #1

输入 #1

2
1 3

输出 #1

2

输入输出样例 #2

输入 #2

3
1 1 1

输出 #2

0

输入输出样例 #3

输入 #3

5
1 2 1 2 1

输出 #3

1

说明/提示

样例 3 解释

符合题意的区间为 \([1,5]\)，该区间的值为 \(\max(1,2,1,2,1)-\min(1,2,1,2,1)=2-1=1\)，为所有区间中值最小的。

数据规模与规定

对于 \(20\) 分的数据，\(N \le 100\)。

对于 \(40\) 分的数据，\(N \le 2000\)。

对于 \(100\%\) 的数据，\(2 \le N \le 10^5\)，\(|A_i| \lt 10^9\)。