비슷한 무게의 검수 상자

문제

물류 창고의 검수 담당자는 새로 들어온 상자 중 두 개를 골라 저울의 측정 결과를 비교하려 한다. 상자는 모두 N개이며, 각 상자의 무게는 정수 단위로 기록되어 있다. 비교 작업에는 무게가 비슷한 상자일수록 적합하므로, 두 상자의 무게 차이가 가능한 한 작아지는 선택을 찾으려 한다. 두 상자를 골랐을 때의 차이는 더 무거운 상자의 무게에서 더 가벼운 상자의 무게를 뺀 값이다. 두 상자의 무게가 같으면 차이는 0이다. 입력에는 무게만 주어지지만 각 위치는 서로 다른 실제 상자를 나타낸다. 따라서 같은 무게가 여러 번 주어져도 상자들을 하나로 합쳐 취급하지 않는다. 또한 하나의 상자를 두 번 골라 비교할 수는 없다. 담당자는 최소 차이뿐 아니라 그 차이를 만드는 상자 쌍이 몇 개인지도 알고 싶어 한다. 두 상자의 선택 순서는 구별하지 않는다. 첫 번째 상자와 두 번째 상자를 고른 선택은 두 번째 상자와 첫 번째 상자를 고른 선택과 같다. 반면 어느 한쪽이라도 다른 실제 상자를 고르면 다른 쌍이다. 여러 쌍이 같은 최소 차이를 만들더라도 대표 쌍 하나만 고르는 것이 아니라 모든 해당 쌍을 센다. 예를 들어 같은 무게의 상자가 세 개 있다면 그 세 상자 안에서는 서로 다른 세 쌍을 만들 수 있다. 다만 전체 입력의 답을 구할 때는 다른 무게의 상자들도 함께 고려해야 한다. 상자들은 입력 순서와 관계없이 자유롭게 선택할 수 있으며, 창고에서 나란히 놓여 있거나 연속해서 입고되었을 필요는 없다. 전체 상자 중 서로 다른 두 개를 골라 만들 수 있는 최소 무게 차이와 그 차이를 만드는 쌍의 수를 출력한다.

입력

첫째 줄에 상자의 수를 나타내는 정수 N이 주어진다. 2 ≤ N ≤ 100,000이다.
둘째 줄에 각 상자의 무게를 나타내는 정수 w_1, w_2, …, w_N이 공백으로 구분되어 주어진다. 1 ≤ w_i ≤ 1,000,000,000이다. 같은 무게가 여러 번 주어질 수 있다.

출력

첫째 줄에 최소 무게 차이와 그 차이를 만드는 서로 다른 상자 쌍의 수를 공백으로 구분하여 출력한다. 상자가 두 개 이상이므로 가능한 쌍은 항상 존재한다. 쌍의 수는 32비트 부호 있는 정수의 범위를 넘을 수 있다.

5
14 8 14 20 8

0 2

5
19 4 10 7 25

3 2

4
6 6 6 6

0 6

출처: Devin.KR 자체 제작