Спасите команды
В олимпиаде участвуют 2n команд из n различных университетов, причем от каждого университета представлено ровно две команды. Все команды сидят за длинным столом в ряд. Сем задал начальное расположение команд.
Юра, как известно, любит дисквалифицировать команды. Он считает, что команду следует дисквалифицировать, если рядом с ней находится команда из того же университета. Команды, в свою очередь, хотят сохранить свои шансы на победу. Чтобы остаться незамеченными Семом, за одну минуту могут поменяться местами только две команды (не обязательно соседние).Помогите командам за минимальное количество минут добиться такого расположения, при котором Юра не сможет дисквалифицировать ни одну команду, то есть никакие две команды из одного университета не будут сидеть рядом. Можно доказать, что при таких условиях это всегда возможно.
Входные данные
Первая строка содержит количество университетов n (2 ≤ n ≤ 10^5).
Вторая строка содержит 2n целых чисел p[1], p[2], ..., p[2n] (1 ≤ p[i] ≤ n), где p[i] обозначает университет команды, сидящей на i-м месте. Гарантируется, что у каждого университета ровно две команды.
Выходные данные
В первой строке выведите минимальное количество минут k, за которое команды смогут достичь желаемого результата.
В каждой из следующих k строк выведите по два целых числа a[i] и b[i] (1 ≤ a[i], b[i] ≤ 2n), обозначающих позиции команд, которые меняются местами в i-ю минуту.
Если существует несколько возможных решений, выведите любое из них.