e-olymp
Задачі

Сортування кісточок

Сортування кісточок

Шарик має велику кількість сортувальників кісточок, які виконують наступну операцію:

prb1095-1

Одного разу він взнав, що з декількох сортувальників кісточок можна сконструювати суперсортувальник. Наприклад, наступна картинка илюструє суперсорувальник четвертого рівня, який складається з шести сортувальників, здатного відсортувати довільні 4 числа.

prb1095-2

Але, як і належить собаці, він є економним у своїх справах. Необхідно визначити найменшу кількість сортувальників кісточок, з яких можна скласти n-суперсортувальник. Вам не потрібен універсальний суперсортувальник, його необхідно сконструювати саме для заданого набору чисел (сортивальники кісточок можна розміщувати на довільній парі ліній).

Також необхідно обчислити кількість інверсій у заданому наборі чисел. (Це число необхідно знати для встановлення ефективності суперсортувальника). Кількість інверсій рівна числу пар (Ai, Aj), що задовольняють умови i < j таAi > Aj.

Вхідні дані

Перший рядок містить кількість чисел N (0 < N100000), які потрібно відсортувати.

Наступні N рядків містять самі числа, по одному числу у рядку. Всі числа різні.

Вихідні дані

Перший рядок містить найменшу кількість сортувальників кісточок, з яких можна скласти бажаний суперсортувальник.

Другий рядок містить кількість інверсій.

prb1095-3

Ліміт часу 0.1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані
Sample 1
3
-3
2
7

Sample 2
4
14
7
2
0
Вихідні дані
Sample 1
0
0

Sample 2
2
6