Сортування кісточок#1095
У Сірки є багато кісткових сортувальників, які виконують таку операцію:
Одного дня він дізнався, що можна збудувати надсортувальник, використовуючи кілька таких кісткових сортувальників. Наприклад, наступне зображення ілюструє надсортувальник рівня , складений з шести сортувальників, який може відсортувати будь-які числа.
Будучи псом, він ощадливий у своїх діях. Необхідно визначити мінімальну кількість кісткових сортувальників, потрібних для побудови -надсортувальника. Не потрібно будувати універсальний надсортувальник; достатньо, щоб він спрацював лише для заданої послідовності чисел (кісткові сортувальники можна розташовувати на будь-якій парі ліній).
Також потрібно обчислити кількість інверсій у заданій послідовності чисел. (Ця величина потрібна для визначення ефективності надсортувальника.) Кількість інверсій — це кількість пар (A_i, A_j), таких що i < j і A_i > A_j.
Перший рядок містить кількість чисел для сортування — (0 < N \leq 100\,000).
У наступних рядках подано по одному числу в кожному. Усі числа різні.
У першому рядку виведіть мінімальну кількість кісткових сортувальників, необхідну для побудови бажаного надсортувальника.
У другому рядку виведіть кількість інверсій.
Приклад 1