P7314 [COCI 2018/2019 #3] Pismo

You are given an array $A$ containing $N$ integers. For an interval $[L,R]$ in this array ($L \lt R$), its value is defined as $\max(A[L],A[L+1],\cdots,A[R])-\min(A[L],A[L+1],\cdots,A[R])$. Find the minimum value among all interval values in the array.

The first line contains a positive integer $N$. The second line contains $N$ integers $A_i$, representing the numbers in the array.

Output the minimum value among all interval values.

#### Explanation for Sample 3 A valid interval is $[1,5]$. The value of this interval is $\max(1,2,1,2,1)-\min(1,2,1,2,1)=2-1=1$, which is the smallest among all intervals. #### Constraints For the testdata worth $20$ points, $N \le 100$. For the testdata worth $40$ points, $N \le 2000$. For $100\%$ of the testdata, $2 \le N \le 10^5$, $|A_i| \lt 10^9$. #### Notes **This problem’s score follows the original COCI settings, with a full score of $70$.** **Translated from [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #3](https://hsin.hr/coci/archive/2018_2019/contest3_tasks.pdf) _T2 Pismo_.** Translated by ChatGPT 5