Катакомби
Піратські катакомби на острові Скарбів було вирито за таким принципом. Після прихованого входу розташована печера, з якої виходять два тунелі - наліво і направо. Кожен із тунелів закінчується печерою, з якої також виходить два тунелі, і т.д. Довжина кожного тунелю дорівнює одиниці. Кінцеві печери, що знаходяться на відстані D від входу, не мають подальших виходів. Ніякі тунелі між собою не перетинаються, та не ведуть до одної печери. Число D називають глибиною катакомб.
У кожній з кінцевих печер приховано один сундук зі скарбом. Перед прибуттям на острів Капітана Джека Сперроу пірати вирішили перемістити ці сундуки згідно з останніми вказівками Капітана. Пірати намалювали план катакомб та пронумерували кінцеві печери зліва направо. Потім для кожного скарбу було встановлено номер печери, в якій він повинен опинитися перед прибуттям Капітана. Після переміщення в кожній печері знову опиниться лише один сундук.
Щоб забезпечити безпеку скарбів, пірати можуть лише обмінювати між собою сундуки з двох печер. Тільки після закінчення одного обміну можна починати інший. Необхідно знайти найменшу сумарну відстань яку піратам потрібно буде нести сундуки, аби розмістити їх потрібним чином.
Вхідні дані
Перший рядок містить одне ціле число D - глибину катакомб (D ≤ 8). Другий рядок містить 2^D різних цілих чисел від 1 до 2^D. Кожне i-те з них ідентифікує номер печери, до якої повинен попасти сундук, що находиться спочатку у печері i.
Вихідні дані
Перший рядок має містити одне ціле число - мінімальну сумарну відстань, яку пройдуть пірати зі скарбами. Другий рядок містить ціле число K - відповідну кількість обмінів. Кожен наступний з K рядків містить два числа, що є номерами печер, між якими відбувається обмін. Обміни повинні бути вказані у тому порядку, в якому вони мають відбуватися.