출발 안내가 가까운 두 노선

문제

한 버스 터미널은 여러 노선의 출발 안내를 하나의 전광판에 표시한다. 이번에 검토할 안내 목록에는 N개 노선이 있으며, 각 노선에는 목록에 적힌 순서대로 1번부터 N번까지 번호가 붙어 있다. 목록에는 각 노선의 출발 시각이 하나씩 기록되어 있다. 같은 노선의 다른 운행은 이번 목록에 포함되지 않는다. 출발 시각은 공통 기준 시각으로부터 지난 분의 수로 표시한다. 모든 시각은 0 이상 99999 이하의 정수이다. 이 값은 날짜가 바뀌어도 계속 증가하는 수이므로 하루를 기준으로 나머지를 구하거나 자정을 넘어 돌아가는 계산을 하지 않는다. 서로 다른 노선의 출발 시각이 같을 수도 있다. 안내 담당자는 출발 시각이 가장 가까운 두 노선을 골라 전광판에서 함께 강조하려 한다. 서로 다른 두 노선의 출발 시각이 각각 x와 y라면 두 시각의 간격은 |x-y|분이다. 출발 시각이 같으면 간격은 0분이다. 노선 번호가 가깝거나 목록에서 이웃해 있다는 사실은 간격에 영향을 주지 않는다. 선택할 수 있는 두 노선의 조합이 여러 개이면 먼저 출발 시각의 간격이 가장 작은 조합을 선택한다. 그 간격까지 같은 조합이 여러 개이면 각 조합의 두 노선 번호를 작은 번호부터 나열하여 비교한다. 첫 번째 번호가 더 작은 조합이 우선이며, 첫 번째 번호도 같으면 두 번째 번호가 더 작은 조합이 우선이다. 이때 번호를 정렬하는 것은 출력할 두 노선 번호에만 적용하며 원래 붙어 있던 번호 자체를 바꾸지 않는다. 모든 노선의 출발 시각이 주어질 때, 선택한 두 노선의 출발 간격과 두 노선 번호를 구하는 프로그램을 작성하라. 노선은 항상 두 개 이상 주어지므로 선택할 조합이 없는 경우는 없다. 같은 시각에 출발하는 노선들도 서로 다른 노선으로 취급해야 한다.

입력

첫째 줄에 정수 N이 주어진다. 2 ≤ N ≤ 40000이다.
둘째 줄에 각 노선의 출발 시각을 나타내는 정수 t_1, t_2, ..., t_N이 공백으로 구분되어 주어진다. 모든 i에 대해 0 ≤ t_i ≤ 99999이다. i번째 값은 i번 노선의 출발 시각이다.

출력

최소 출발 간격, 선택한 두 노선 중 작은 번호, 큰 번호를 순서대로 한 줄에 공백으로 구분하여 출력한다. 최소 간격이 같은 경우에는 지문에 명시된 번호 비교 규칙을 따른다.

5
40 12 30 20 41

1 1 5

6
8 3 8 3 8 3

0 1 3

2
0 99999

99999 1 2

출처: Devin.KR 자체 제작