Cho dãy số \(A\) gồm \(n\) số nguyên \(a_1, a_2,..., a_n\) mỗi số có giá trị tuyệt đối không quá \(10^9\). Hãy tìm hai chỉ số \(i\) và \(j\) khác nhau sao cho \(|a_i - a_j|\) là nhỏ nhất \((1 \le i, j \le n, i \ne j)\).

Dữ liệu vào:

• Dòng đầu tiên ghi một số nguyên \(n (2 \le n \le 5 \times 10^6)\) là số phần tử trong dãy;
• Dòng thứ hai ghi \(n\) số nguyên \(a_1, a_2,... a_n (|a_i| \le 10^9, 1 \le i \le n)\) cách nhau ít nhất một dấu cách.

Dữ liệu ra: là một số nguyên duy nhất là giá trị \(|a_i -a_j|\) nhỏ nhất tìm được.

Ràng buộc:

• 50% số test ứng với 50% số điểm có \(n \le 2 \times 10^3\).
• 50% số test còn lại ứng với 50% số điểm không có ràng buộc gì thêm.

Input

6
-4 3 -9 0 10 5

Output

2

Giải thích

Hai chỉ số cần tìm là 2 và 6, \(|a_2 - a_6| = 2\)

Input

3
1 1 1

Output

2
0

Giải thích

Hai chỉ số cần tìm là 1 và 3, \(|a_1 - a_3| = 0\)