Description

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.

Input Format

The first line contains a positive integer $N$.

The second line contains $N$ integers $A_i$, representing the numbers in the array.

Output Format

Output the minimum value among all interval values.

2
1 3

2

3
1 1 1

0

5
1 2 1 2 1

1

Hint

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 CONTEST #3 T2 Pismo.

Translated by ChatGPT 5