The input includes multiple test cases. In each test case, the first line contains one integers N. The next line contains N integers.
Hint:
The sorting algorithms in O(n lg n) don’t work.
To avoid Time Limit Exceeded in Input/Output process, try to use scanf / printf to replace cin / cout.
1 <= N <= 2*106
0 <= Xi <= 104
Case 1: 1 <= N <= 105
Case 2: 1 <= N <= 106
Case 3: 1 <= N <= 106
Case 4: 1 <= N <= 2*106