In a small village besides Đakovo lives Kasap. While agriculture is his branch, love and destiny, in his free time Kasap solves tasks in competitive programming and is doing very well. Particularly interesting are the tasks involving data structures.

On a sunny summer day, Kasap's friend Mirko sent him a letter we carry forward entirely:

"My dear Kasap,

I hope you tolerate well these hot summer days. I'm writing this letter because I have a problem. One friend gave me a hard task the other day that I have not managed to solve yet. Since I know that you love this sort of task, I would ask you for help because I do not want to embarrass myself in front of my friend. In the task, there is an array ~A~ consisting of ~N~ integers. You should find an interval of the minimum value. The value of the interval ~[L, R]~ is defined as the difference between the maximum and minimum value of the numbers in that interval: ~\max(A[L], A[L+1], \dots, A[R]) - \min(A[L], A[L+1], \dots, A[R])~. I will remind you that we observe only the intervals in which ~L~ is strictly less than ~R~.

Thank you, Mirko"

After a week of solving, Kasap has not yet managed to solve the task and asks you to help him.

Input

In the first line of input there is a positive integer ~N~ ~(2 \le N \le 100\,000)~.

In the second line of input there are ~N~ integers, which absolute value is less than ~10^9~.

Output

Print the minimum value of an interval.

Scoring

In the test samples worth 20 points it will hold ~N \le 100~.

In the test samples worth 40 points it will hold ~N \le 2\,000~.

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

Explanation for Sample Output 3

The maximum at interval ~[1, 5]~ is ~2~, while the minimum on the same interval is ~1~, so the value of that interval is ~2 - 1 = 1~, which is also the minimum possible value of an interval.