Mr Hola is back with some trouble for BB. He said BB that, he will forgive him only if BB is able to solve a problem.He gave him an unsorted array A={a1,a2,a3...an}, and asked him find the pair of elements that have the smallest absolute difference between them. Also If there are multiple pairs, find them all.Help BB to solve this problem.
Input:
The first line of input contains a single integer,N , representing the length of array A. In the second line, there are N space-separated integers,a1,a2,a3...an , representing the elements of array A.
Output:
Output the pairs of elements with the smallest difference. If there are multiple pairs, output all of them in ascending order, all on the same line (consecutively) with just a single space between each pair of numbers. If there's a number which lies in two pair, print it two times.
Constraints:
- 2 ≤ n ≤ 25000
- -10^7 ≤ 10^7
- Ai ≠ Aj where 1 ≤ i ≤ j ≤ N
(-470) - (-520) = 30 - (-20) = 50, which is the smallest difference.
Other example:
Input
4
5 4 3 2
Output
2 3 3 4 4 5
Here, the minimum difference will be 1. So valid pairs are (2, 3), (3, 4), and (4, 5). So we have to print 2 once, 3 and 4 twice each, and 5 once.
