题目描述
给定一个包含 N 个整数的数组 A。
该数组中一个区间 [L,R] (L<R)的值定义为 max(A[L],A[L+1],⋯,A[R])−min(A[L],A[L+1],⋯,A[R])。
求该数组中所有区间值的最小值。
输入格式
第一行输入正整数 N。
第二行输入 N 个整数 Ai,表示数组中的数。
输出格式
输出所有区间值的最小值。
提示
样例 3 解释
符合题意的区间为 [1,5],该区间的值为 max(1,2,1,2,1)−min(1,2,1,2,1)=2−1=1,为所有区间中值最小的。
数据规模与规定
对于 20 分的数据,N≤100。
对于 40 分的数据,N≤2000。
对于 100% 的数据,2≤N≤105,∣Ai∣<109。
说明
本题分值按 COCI 原题设置,满分 70。
题目译自 COCI2018-2019 CONTEST #3 T2 Pismo。