WishingBone has many bone sorters that can perform function as follows:
One day he happened to find out he could use several such bone sorters to construct super bone sorters. For instance, the figure below illustrates one way to construct a level 4 super bone sorter with six bone sorters, which can sort 4 arbitrary numbers.
But, as a doggie, he is sure thrift on bones. So he wonders what the minimal number of bone sorters to construct an n-super bone sorter could be. Besides, he does not actually need a general sorter, but one on some numbers he knows in advance, so that you may take this advantage in calculating the solution. (Suppose bone sorter can be placed on any pair of lines.)
By the way, he is also eager to know the inversion number of the original numbers. (He wants this value to evaluate the efficiency of his bone sorter.) Inversion number is the number of such pairs (Ai, Aj) that satisfies iAj.
Input
The first line of input is an integer N ( 0 < N <= 100000 ), which is the number of integers to be sorted.
The following N lines contain one integer on each line. All integers are distinct.
Output
The first line of output is the minimal number of bone sorters to construct the super sorter desired.
The second line is the inversion number.
Sample Input
3
-3
2
7
Sample Output
0
0
Sample Input
4
14
7
2
0
Sample Output
2
6
