가까운 관리 번호 두 권

문제

한 도서관에서는 책마다 서로 다른 양의 정수 관리 번호를 붙인다. 오늘 반납된 책 N권은 아직 반납 수레에 섞여 있으며, 사서는 이 가운데 두 권을 골라 작은 점검대에 올려놓으려고 한다. 점검대에는 책을 정확히 두 권만 놓을 수 있다. 사서는 관리 번호가 가까운 책끼리 점검하면 기록을 확인하기 편하다고 생각하여, 두 관리 번호의 차이가 가장 작은 쌍을 고르기로 했다. 두 책의 관리 번호가 각각 a와 b이고 a가 b보다 작다면, 이 두 책의 번호 차이는 b-a이다. 가능한 모든 두 권의 조합 가운데 이 차이가 가장 작은 조합을 선택한다. 책이 수레에 놓인 순서는 선택 기준에 영향을 주지 않는다. 입력에서도 관리 번호는 크기순으로 주어지지 않을 수 있으므로 입력에서 이웃한 두 책만 비교해서는 안 된다. 가장 작은 차이를 가지는 쌍이 여러 개라면 두 번호 중 작은 번호가 더 작은 쌍을 선택한다. 모든 관리 번호는 서로 다르므로 이 기준까지 적용하면 선택할 쌍이 하나로 결정된다. 예를 들어 번호 차이가 같은 두 쌍이 있더라도 각 쌍에서 작은 번호를 비교하여 어느 쌍을 고를지 결정할 수 있다. 선택한 두 번호를 출력할 때에는 작은 번호를 먼저 출력해야 한다. 오늘 반납된 책은 적어도 두 권이므로 선택할 수 있는 쌍이 없는 경우는 없다. 관리 번호 사이에 다른 정수가 빠져 있어도 상관없으며, 번호를 새로 매기거나 책을 추가하지 않는다. 또한 관리 번호가 연속된 두 권이 반드시 존재하는 것도 아니다. 주어진 책만을 대상으로 선택 규칙을 적용하여 점검대에 놓을 두 권의 관리 번호를 구한다.

입력

첫째 줄에 반납된 책의 수 N이 주어진다.
둘째 줄에 N권의 관리 번호가 공백으로 구분되어 주어진다.
N은 정수이며 2 ≤ N ≤ 1,000이다. 각 관리 번호는 1 이상 100,000 이하의 정수이고, 모든 관리 번호는 서로 다르다.

출력

선택한 두 책의 관리 번호를 작은 번호부터 공백으로 구분하여 한 줄에 출력한다. 번호 차이가 최소인 쌍이 여러 개이면 두 번호 중 작은 번호가 가장 작은 쌍을 출력한다.

5
42 17 30 19 8

17 19

6
26 10 18 2 34 42

2 10

2
99999 1

1 99999

출처: Devin.KR 자체 제작