Bone Sort#1095
Sirka has many bone sorters that perform the following operation:
One day, he found out that it is possible to construct a super sorter using several such bone sorters. For example, the following picture illustrates a level super sorter composed of six sorters, which can sort any numbers.
Being a dog, he is thrifty in his actions. It is necessary to determine the minimal number of bone sorters required to construct an -super sorter. You do not need a universal super sorter; it is only required for the given set of numbers (the bone sorters can be placed on any pair of lines).
You must also compute the number of inversions in the given set of numbers. (This value is needed to determine the efficiency of the super sorter.) The number of inversions is the number of pairs (A_i, A_j) such that i < j and A_i > A_j.
The first line contains the number of numbers to be sorted, (0 < N \leq 100\,000).
The following lines contain one number per line. All numbers are distinct.
The first line contains the minimal number of bone sorters required to construct the desired super sorter.
The second line contains the number of inversions.
Example 1