가장 가까운 두 출발

문제

한 버스 노선의 담당자가 하루 동안 차고지에서 출발하는 버스들의 시각을 점검한다. 각 출발 시각은 그날 0시부터 지난 분으로 기록되어 있다. 담당자는 출발 시각의 차이가 가장 작은 두 버스를 찾아 안내판에 주의 표시를 하려고 한다. 기록은 예약이 접수된 순서로 전달되므로, 입력에 적힌 순서와 실제 출발 순서는 서로 다를 수 있다. 서로 다른 두 버스의 출발 간격은 두 출발 시각 중 큰 값에서 작은 값을 뺀 값이다. 예를 들어 출발 시각이 73과 81이면 간격은 8분이다. 같은 시각에 출발하는 버스가 여러 대 있을 수도 있다. 이들은 각각 별개의 버스이며, 같은 시각에 출발하는 두 버스의 간격은 0분이다. 한 버스를 두 번 골라 간격을 계산할 수는 없다. 담당자에게 필요한 것은 버스의 번호나 출발 시각 자체가 아니라, 가능한 모든 두 버스의 조합에서 얻을 수 있는 가장 작은 간격이다. 가장 작은 간격을 만드는 조합이 여러 개라도 그 간격을 한 번만 출력한다. 기록된 버스가 한 대뿐이면 두 버스를 고를 수 없으므로 -1을 출력한다. 모든 기록은 같은 날의 출발을 나타낸다. 하루의 마지막 출발과 다음 날의 첫 출발을 이어서 생각하지 않으며, 시각이 작은 버스가 항상 먼저 출발한다. 입력된 기록을 실제 출발 순서대로 정리했을 때 이웃한 버스 사이의 간격을 살펴보면 필요한 값을 구할 수 있다. 주어진 모든 출발 기록을 이용하여 담당자가 표시할 최소 간격을 구하는 프로그램을 작성한다.

입력

첫째 줄에 버스의 수 N이 주어진다. 둘째 줄에 N개의 출발 시각 T₁, T₂, …, Tₙ이 공백으로 구분되어 주어진다.
N과 모든 출발 시각은 정수이며, 1 ≤ N ≤ 1,000, 0 ≤ Tᵢ ≤ 1,439이다. 같은 출발 시각이 여러 번 주어질 수 있다.

출력

서로 다른 두 버스의 출발 간격 중 최솟값을 분 단위 정수로 출력한다. N이 1이면 -1을 출력한다.

5
91 24 68 30 115

6

4
600 420 600 900

0

1
735

-1

출처: Devin.KR 자체 제작