Wesley는 부활절을 맞아 $N$개의 원소로 이루어진 배열 $(a_1, a_2, \dots, a_N)$을 선물 받았고, 이를 정렬($a_1 \le a_2 \le \dots \le a_N$이 되도록)하고 싶어 합니다.

심심해진 Wesley는 스스로에게 더 어려운 조건을 걸기로 했습니다. 두 원소의 절댓값 차이가 $K$ 이하일 때만 두 원소를 교환할 수 있도록 제한한 것입니다. 원소들의 위치는 상관없으며, 두 원소의 절댓값 차이가 $K$ 이하이기만 하면 Wesley는 그들을 교환할 수 있습니다.

안타깝게도 Wesley는 배열을 정렬하는 것이 불가능할 수도 있다는 사실을 금방 깨달았습니다. 그래서 그는 배열을 정렬할 수 있게 만드는 최소한의 $K$ 값이 무엇인지 궁금해졌습니다.

입력

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

다음 줄에는 배열의 원소인 $N$개의 정수 $a_1, a_2, \dots, a_N$이 주어집니다($1 \le a_i \le 10^{18}$).

출력

배열을 정렬할 수 있게 만드는 최소한의 $K$ 값을 출력하십시오. 만약 원소들이 이미 정렬되어 있다면 0을 출력해야 합니다.

예제

입력 1

8
1 4 4 2 7 14 12 10

출력 1

2