Wesley nhận được một mảng gồm $N$ phần tử $(a_1, a_2, \dots, a_N)$ nhân dịp lễ Phục sinh và rất muốn sắp xếp nó (sao cho $a_1 \le a_2 \le \dots \le a_N$).

Vì cảm thấy nhàm chán, Wesley quyết định làm khó bản thân bằng cách chỉ cho phép hoán đổi hai phần tử nếu hiệu tuyệt đối giữa chúng nhỏ hơn hoặc bằng $K$. Lưu ý rằng các phần tử có thể ở bất kỳ vị trí nào; miễn là hiệu tuyệt đối giữa chúng nhỏ hơn hoặc bằng $K$, Wesley có thể hoán đổi chúng.

Thật không may, Wesley nhanh chóng nhận ra rằng có thể không sắp xếp được mảng. Sau đó, cậu tự hỏi: giá trị nhỏ nhất của $K$ cần thiết để có thể sắp xếp mảng là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$, số lượng phần tử trong mảng ($1 \le N \le 2 \cdot 10^5$).

Dòng tiếp theo chứa $N$ số nguyên $a_1, a_2, \dots, a_N$, chính là mảng đó ($1 \le a_i \le 10^{18}$).

Dữ liệu ra

In ra giá trị nhỏ nhất của $K$ cần thiết để có thể sắp xếp mảng. Nếu các phần tử đã được sắp xếp, bạn nên in ra 0.

Ví dụ

Dữ liệu vào 1

8
1 4 4 2 7 14 12 10

Dữ liệu ra 1

2