Церемонія відкриття

Директор церемонії відкриття Кубка Векуа склав план представлення $n$ команд з різних університетів: на сцену вийде послідовність з $2n$ осіб. Кожний університет представляють двоє учасників у цій послідовності: перший несе табличку з назвою університету мовою своєї країни, а другий — бажано дитина, згідно з баченням режисера — тримає повітряну кульку (за аналогією з традицією ACM ICPC). Таким чином, у послідовності є $n$ людей з табличками та $n$ дітей з кульками.

Учасники вже вишикувалися в чергу, але послідовність виявилася безладною: місцями поряд ідуть двоє власників табличок, а десь зібрані групи дітей. Оскільки учасників багато, дати команди всім відразу було б хаотично, тому режисер може наказати лише двом сусіднім людям помінятися місцями. Порядок представлення університетів не має принципового значення (це відкриття, а не оголошення результатів), і мета режисера — добитися, щоб послідовність починалася з власника таблички, а далі ніде не зустрічалися поруч двоє власників табличок чи двоє дітей з кульками. Директор хоче визначити мінімальну кількість перестановок, потрібних для досягнення цієї черговості.