무게가 가까운 택배 두 상자

문제

택배 작업장에서 운반 장치의 시험 운행을 준비하고 있다. 시험에 사용할 장치에는 상자를 하나씩 올리는 받침대가 두 개 있다. 담당자는 두 받침대에 실리는 무게가 가능한 한 비슷하도록, 작업장에 도착한 상자 중 서로 다른 두 상자를 골라 시험하려고 한다. 모든 상자는 이미 포장이 끝났으며 상자를 열거나 내용물을 나누는 작업은 하지 않는다. 작업장에는 N개의 상자가 있고 각 상자의 무게가 그램 단위의 양의 정수로 기록되어 있다. 두 상자를 골랐을 때의 무게 차이는 무거운 상자의 무게에서 가벼운 상자의 무게를 뺀 값이다. 두 상자의 무게가 같다면 무게 차이는 0이다. 입력에서 같은 무게가 여러 번 나오면 그 값들은 서로 다른 상자의 무게를 나타내므로, 같은 무게를 가진 상자 두 개를 고르는 것도 가능하다. 상자의 도착 순서는 선택에 영향을 주지 않는다. 입력에서 이웃하지 않는 상자도 함께 고를 수 있으며, 어느 상자를 어느 받침대에 놓는지도 무게 차이에 영향을 주지 않는다. 상자의 크기나 목적지에 따른 제한은 없고 오직 기록된 무게만 비교한다. 하나의 상자를 두 번 골라 두 받침대에 동시에 놓을 수는 없다. 서로 다른 두 상자를 고르는 모든 방법 중에서 얻을 수 있는 가장 작은 무게 차이를 구한다. 최솟값을 만드는 상자 쌍이 여러 개여도 상자의 번호나 쌍의 개수는 출력하지 않고, 최소 무게 차이만 한 번 출력한다. 상자는 항상 두 개 이상 주어지므로 선택할 수 있는 쌍이 없는 경우는 없다. 가능한 모든 쌍을 직접 비교하지 않고도 답을 찾는 방법을 생각해 본다.

입력

첫째 줄에 상자 수 N이 주어진다. 2 ≤ N ≤ 50,000이다.
둘째 줄에 각 상자의 무게 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 1 ≤ A_i ≤ 1,000,000이다.
입력의 모든 수는 정수다.

출력

서로 다른 두 상자를 골랐을 때 가능한 최소 무게 차이를 정수 하나로 출력한다. 같은 무게의 상자가 두 개 이상 있으면 0을 출력한다.

5
84 31 70 46 49

3

4
105 27 105 61

0

2
1 1000000

999999

출처: Devin.KR 자체 제작