P7314 [COCI 2018/2019 #3] Pismo

给定一个包含 $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$，表示数组中的数。

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

#### 样例 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$。 #### 说明 **本题分值按 COCI 原题设置，满分 $70$。** **题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #3](https://hsin.hr/coci/archive/2018_2019/contest3_tasks.pdf) _T2 Pismo_。**