Minimum Interval Value in an Array

You are given an array A of N integers. A contiguous interval [L,R] (with L < R) in the array has a value defined as:

\(\max(A[L], A[L+1], \ldots, A[R]) - \min(A[L], A[L+1], \ldots, A[R])\)

Your task is to find the minimum value among all such intervals.

Note: Since an interval must contain at least two elements, you only need to consider intervals where L < R.

inputFormat

The first line contains a single integer N, representing the number of elements in the array.

The second line contains N space-separated integers representing the elements of the array A.

outputFormat

Output a single integer, which is the minimum value among all valid intervals.

sample

4
1 3 2 5

1