부활절 선물

Wesley는 부활절 선물로 $N$개의 원소로 이루어진 배열($a_1, a_2, \ldots, a_N$)을 받았고, 이 배열을 정렬하고 싶어 한다(즉 $a_1 \le a_2 \le \ldots \le a_N$이 되도록). 지루해진 Wesley는 두 원소의 절댓값 차이가 $K$ 이하일 때만 두 원소를 교환할 수 있다는 규칙을 스스로에게 추가해 난이도를 높였다. 원소의 위치는 상관없다. 두 원소의 절댓값 차이가 $K$ 이하이기만 하면 Wesley는 그 둘을 교환할 수 있다.

안타깝게도 Wesley는 배열을 정렬하는 것이 불가능할 수도 있다는 사실을 곧 깨달았다. 그래서 궁금해졌다. 배열을 정렬할 수 있게 하려면 $K$의 최솟값이 얼마여야 할까?

첫째 줄에는 배열의 원소 개수인 정수 $N$이 주어진다($1 \le N \le 2 \cdot 10^5$).

둘째 줄에는 $N$개의 정수 $a_1, a_2, \ldots, a_N$이 주어진다. 이는 배열 자체이다($1 \le a_i \le 10^{18}$).

배열을 정렬할 수 있게 하는 $K$의 최솟값을 출력한다. 배열이 이미 정렬되어 있다면 $0$을 출력한다.