Alex has some pillars of different heights. He is trying to arrange the pillars in descending order according to their heights. Recently he has learned Divide & Conquer (D&C) algorithm strategy. There is a sorting algorithm in Divide & Conquer whose special case is, f(n) = O(n^2). So, now you have to help Alex to sort the pillars with that particular D&C algorithm. Finally, you need to display k, the number of times the division will be required for sorting and also display the heights in descending order.

Input: At the first line, you have to take the number of pillars, N (1<=N<=100), then, in the second line, you have to take N integer numbers indicating the heights of the pillars.

Output: You need to display k and the height of the pillars in descending order

Sample Input:

6

6 3 8 11 2 77

Sample Output:

3

77 11 8 6 3 2