Water Stop Gap
Problem
Water stations stand along a trail with n stops. Station i is at position p_i metres from the trailhead, and several stations can share a position. A race marshal wants the smallest distance between any two different stations, and the number of pairs of stations that are exactly that close.
Two stations at the same position are at distance 0. A pair means two different stations, and the pair (i, j) is the same as the pair (j, i).
Input
The first line has an integer n. The second line has n integers p_1 ... p_n, in any order.
Output
Print two integers separated by a space: the smallest distance d between two different stations, and the number of pairs of stations whose distance is exactly d.
Constraints
- 2 ≤ n ≤ 150000
- -109 ≤ pi ≤ 109
- The number of pairs can be larger than 32 bits.
Notes
In the first example the sorted stations are at 1, 4, 6, 8 and 12. The smallest distance between two stations is 2, and exactly two pairs are that close: the stations at 4 and 6, and the stations at 6 and 8. So the answer is 2 2. The number of pairs can be larger than 32 bits.