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

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

1 секунда

128 мегабайтів

Дуже легка

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

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

Вхідні дані

Перший рядок містить кількість університетів $n$ ( $2 \leq n \leq 1 0^{5}$ 2 \leq n \leq 10^5).

Другий рядок містить $2 n$ цілих чисел $p_{1}, p_{2}, \dots, p_{2 n}$ p_1, p_2, \ldots, p_{2n} ( $1 \leq p_{i} \leq n$ 1 \leq p_i \leq n) - університет команди, яка сидить на $i$ -му місці. Гарантується, що в кожного університету рівно дві команди.

Вихідні дані

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

У кожному з наступних $k$ рядках виведіть по два цілі числа $a_{i}$ a_i та $b_{i}$ b_i ( $1 \leq a_{i}, b_{i} \leq 2 n$ 1 \leq a_i, b_i \leq 2n) - позиції команд, які міняються місцями в $i$ -ту хвилину.

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

Приклади

Приклад 1

Приклад 2