Problem Description

Given an array \( A \) containing \( N \) integers.

The value of a segment \([L, R]\) (\(L < R\)) in the array 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 segments in the array.

Input Format

The first line contains a positive integer \( N \).

The second line contains \( N \) integers \( A_i \), representing the elements of the array.

Output Format

Output the minimum value of all segment values.

Sample Input and Output

Sample Input #1

2
1 3

Sample Output #1

2

Sample Input #2

3
1 1 1

Sample Output #2

0

Sample Input #3

5
1 2 1 2 1

Sample Output #3

1

Notes

Sample 3 Explanation

The segment \([1, 5]\) meets the criteria, and its value is \(\max(1, 2, 1, 2, 1) - \min(1, 2, 1, 2, 1) = 2 - 1 = 1\), which is the minimum value among all segments.

Data Size and Constraints

For 20 points, \( N \leq 100 \).

For 40 points, \( N \leq 2000 \).

For 100% of the points, \( 2 \leq N \leq 10^5 \), \( |A_i| < 10^9 \).

Notes

This problem's score is set according to the original COCI contest, with a full score of 70.

The problem is translated from COCI2018-2019 CONTEST #3 T2 Pismo.

见题面 Input 部分

见题面 Output 部分