Сортировка костей
Шарик имеет большое количество сортировщиков костей, которые совершают следующую операцию:
Однажды он узнал, что из нескольких сортировщиков костей можно сконструировать суперсортировщика. Например, следующая картинка иллюстрирует суперсортировщика четвертого уровня, состоящего из шести сортировщиков, способного отсортировать любые 4 числа.
Но, как и положено собаке, он является экономным в своих делах. Необходимо определить наименьшее количество сортировщиков костей, из которых можно составить n-суперсортировщика. Вам не нужен общий суперсортировщик, его необходимо сконструировать именно для заданного набора чисел (сортировщики костей можно располагать на любой паре линий).
Также необходимо вычислить количество инверсий в исходном наборе чисел. (Это число необходимо знать для установления эффективности суперсортировщика). Количество инверсий равно числу пар (Ai, Aj), удовлетворяющих условия i < j и Ai > Aj.
Входные данные
Первая строка содержит количество чисел N (0 < N ≤ 100000), которое следует отсортировать.
Следующие N строк содержат сами числа, по одному числу в строке. Все числа разные.
Выходные данные
Первая строка содержит наименьшее количество сортировщиков костей, из которых можно составить желаемый суперсортировщик.
Вторая строка содержит количество инверсий.
