Given N integers to be sorted in non-decreasing order. In connection with the norms of the SES, among the numbers there will not be two, the difference between which exceeds 10^{7}.

Input

The first line of the input file contains the integer N. (1 <= N <= 100000), the second line – N integers not exceeding 2*10^{9} in modulo. No two differ by more than 10^{7}.