운동 기록이 가장 가까운 두 회원

문제

한 헬스장은 회원들이 같은 운동 프로그램을 체험한 뒤 기록한 점수를 모아 두었다. 이번에는 서로 기록이 비슷한 두 회원을 골라 함께 운동하는 시범 수업을 진행하려 한다. 후보 회원은 N명이며, 각 회원에게는 1번부터 N번까지 서로 다른 번호가 붙어 있다. 각 회원의 점수는 음이 아닌 정수 하나로 주어진다. 두 회원의 기록 차이는 두 점수 중 큰 값에서 작은 값을 뺀 값이다. 점수가 같으면 기록 차이는 0이다. 운영 담당자는 가능한 모든 두 회원의 조합 가운데 기록 차이가 가장 작은 조합을 찾고, 그러한 조합이 모두 몇 개인지 확인하려 한다. 한 조합에는 서로 다른 회원 두 명이 들어가야 하므로, 같은 회원을 두 번 선택할 수는 없다. 조합을 셀 때 두 회원을 고르는 순서는 구분하지 않는다. 예를 들어 2번 회원과 5번 회원을 고른 조합은 5번 회원과 2번 회원을 고른 조합과 같다. 그러나 회원 번호가 다르면 점수가 같더라도 서로 다른 회원이다. 따라서 같은 점수를 받은 회원이 여러 명 있으면 그들 가운데 서로 다른 두 명을 고르는 각각의 조합을 모두 세어야 한다. 이번 계산은 여러 쌍을 동시에 편성하는 작업이 아니다. 시범 수업에 사용할 단 하나의 조합을 고를 수 있는 경우들을 세는 작업이다. 따라서 어떤 회원이 서로 다른 여러 후보 조합에 포함되어도 각 조합은 유효하다. 같은 회원이 여러 조합에 등장한다는 이유로 일부 조합을 제외하지 않는다. 회원들의 점수가 입력된 순서는 회원 번호를 나타낼 뿐, 두 회원을 함께 고를 수 있는지에는 영향을 주지 않는다. 모든 회원 사이에서 조합을 만들 수 있다. N은 2 이상이므로 선택할 수 있는 조합은 항상 하나 이상 존재한다. 회원들의 점수가 주어질 때, 가장 작은 기록 차이와 그 차이를 갖는 서로 다른 회원 조합의 개수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N이 주어진다.
둘째 줄에 1번부터 N번까지 각 회원의 점수 A1, A2, ..., AN이 공백으로 구분되어 주어진다.
2 ≤ N ≤ 100,000이다.
각 Ai는 0 이상 1,000,000,000 이하인 정수이다.

출력

가장 작은 기록 차이와 그 차이를 갖는 회원 조합의 개수를 공백으로 구분하여 한 줄에 출력한다. 가장 작은 차이를 갖는 조합이 여러 개이면 그 개수를 모두 센다.

6
18 7 12 23 31 40

5 2

7
20 8 20 8 20 31 45

0 4

2
0 1000000000

1000000000 1

출처: Devin.KR 자체 제작