Mind the Gap

Mika는 친구들과 Mind 게임을 하고 있다.

이 게임은 카드로 진행되며, 각 카드에는 정수 하나가 적혀 있다. 카드에 적힌 값은 모두 서로 다르다. 플레이어들은 카드를 계속 내면서 테이블 위에 카드 더미 하나를 쌓는다. 처음에 더미에는 정수 $0$이 적힌 카드 한 장이 있다. 각 플레이어는 $1$부터 $10^9$까지의 값이 적힌 카드 한 장씩 받는다. 그다음 플레이어들은 임의의 순서로 카드를 내기 시작한다. 플레이어가 카드를 내면 더미 맨 위에 카드를 놓는다. 목표는 카드 값이 아래에서 위로 갈수록 커지도록 모든 카드를 내는 것이다. 카드를 내지 못한 플레이어가 있거나 더미가 증가하지 않으면 플레이어들은 지고, 그렇지 않으면 이긴다. 카드를 나눠 준 뒤에는 플레이어들 사이에 어떤 의사소통도 허용되지 않는다.

Mika와 친구들은 전략을 하나 생각해 냈다. 게임 전에 정수 $d$ 하나를 정한다. 게임 중에 플레이어의 카드 값이 $x$이고 더미 맨 위의 값이 $y$일 때, $x - y \le d$이면 그 플레이어는 카드를 낸다. $x - y > d$이면 카드를 내지 않는다. 여러 플레이어가 동시에 카드를 내면 이 카드들은 어떤 순서로든 더미 맨 위에 놓일 수 있으며, 이 순서는 플레이어들이 제어할 수 없다.

플레이어들에게 나눠 줄 카드 값들이 주어진다. 플레이어들의 전략이 승리를 보장하도록 하는 정수 $d$를 구하시오.

첫째 줄에는 Mind 게임을 하는 플레이어 수 $n$이 주어진다 ($3 \le n \le 100\,000$).

둘째 줄에는 플레이어들에게 나눠 줄 카드 값 $n$개가 주어진다.

주어진 카드 값은 모두 서로 다르고 양수이며 $10^9$를 넘지 않는다.

Mika와 친구들이 이 전략으로 게임에서 승리를 보장하기 위해 사용해야 하는 정수 $d$를 출력한다. 그러한 $d$가 없으면 $0$을 출력한다. $d$의 값이 여러 개라면 아무 것이나 출력한다.

첫 번째 예시에서 $d = 3$도 정답이 될 수 있다.