eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Врятуйте команди

Врятуйте команди

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

В олiмпiадi бере участь 2n команд з n рiзних унiверситетiв, з кожного унiверситету рiвно двi команди. Усi команди сидять за довгим столом у ряд. Сем визначив початкове розмiщення команд.

Як вiдомо, Юра дуже любить дисквалiфiковувати команди. Вiн вважає, що команду слiд дисквалiфiкувати, якщо поруч з нею сидить команда з того ж унiверситету. Команди ж хочуть зберегти свої шанси на перемогу. Щоб бути непомiченими Семом, за одну хвилину тiльки двi команди (необов’язково сусiднi) можуть помiнятись мiсцями.Допоможiть командам за мiнiмальну кiлькiсть хвилин досягти такого стану, коли Юра не зможе дисквалiфiкувати жодну команду, тобто коли жоднi двi команди з одного унiверситету не сидять поруч. Можна довести, що при таких обмеженнях це завжди можливо зробити.

Вхiдні дані

Перший рядок мiстить кiлькiсть унiверситетiв n (2n10^5).

Другий рядок мiстить 2n цiлих чисел p[1], p[2], ..., p[2n] (1p[i]n) - унiверситет команди, яка сидить на i-му мiсцi. Гарантується, що в кожного унiверситету рiвно двi команди.

Вихiдні дані

У першому рядку виведiть мiнiмальну кiлькiсть хвилин k, за яку команди зможуть досягти бажаного результату.

У кожному з наступних k рядках виведiть по два цiлi числа a[i] та b[i] (1a[i], b[i]2n) - позицiї команд, якi мiняються мiсцями в i-ту хвилину.

Якщо iснує кiлька можливих вiдповiдей, то виведiть будь-яку з них.

Приклад

Вхідні дані #1
4
1 2 2 4 1 3 3 4
Вихідні дані #1
1
3 6
Вхідні дані #2
2
1 2 1 2
Вихідні дані #2
0
Джерело 2019 ACM, SEERC, 1/8 фiналу, 13 квiтня