Trong một ngôi làng nhỏ gần Đakovo sống một người đàn ông tên Kasap. Trong khi nghề nghiệp chính của anh là nông nghiệp, tình yêu và số phận, vào thời gian rảnh rỗi Kasap giải các bài toán trong lập trình cạnh tranh và làm rất tốt. Đặc biệt là những bài toán liên quan đến cấu trúc dữ liệu.

Một ngày hè nắng nóng, người bạn của Kasap, Mirko, đã gửi cho anh một lá thư chúng ta chuyển tiếp toàn bộ:

"Chào Kasap thân mến của tôi,

Tôi hy vọng bạn chịu đựng được những ngày hè nóng bức này. Tôi viết thư này vì tôi gặp một vấn đề. Một người bạn đã đưa cho tôi một bài toán khó ngày hôm trước mà tôi chưa giải quyết được. Vì tôi biết rằng bạn thích những loại bài toán này, tôi muốn nhờ bạn giúp đỡ vì tôi không muốn làm mình xấu hổ trước bạn bè của mình. Trong bài toán có một mảng ~A~ gồm ~N~ số nguyên. Bạn cần tìm một khoảng của giá trị tối thiểu. Giá trị của khoảng ~[L, R]~ được xác định là sự khác biệt giữa giá trị lớn nhất và nhỏ nhất của các số trong khoảng đó: ~max(A[L], A[L+1], …, A[R]) - min(A[L], A[L+1], …, A[R])~. Tôi nhắc lại rằng chúng ta chỉ quan sát các khoảng mà ~L~ nhỏ hơn ~R~.

Cảm ơn bạn, Mirko"

Sau một tuần giải quyết, Kasap vẫn chưa giải quyết được bài toán và nhờ bạn giúp đỡ.

Input

• Trong dòng đầu tiên của đầu vào có một số nguyên dương ~N~ ~(2 \leq N \leq 100 000)~.
• Trong dòng thứ hai của đầu vào có ~N~ số nguyên, với giá trị tuyệt đối nhỏ hơn ~10^9~.

Onput

In ra giá trị tối thiểu của một khoảng.

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

Giải thích

Trong test thứ ba, giá trị lớn nhất trong khoảng ~[1, 5]~ là ~2~, trong khi giá trị nhỏ nhất trong cùng một khoảng là ~1~, vì vậy giá trị của khoảng đó là ~2 - 1 = 1~, cũng là giá trị nhỏ nhất có thể của một khoảng.