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