Сноубординг
Погода у перші дні олімпіади не радувала ні спортсменів, ні глядачів. Але ось кому прйишлось дійсно важко, так це організаторам. Проливний дощ і теплі дні знищили більшу частину снігу на трасі для сноуборда. Із-за цього організатори були змушені декілька разів переносити змагання, намагаючись відновити трасу при допомозі запасів снігу.
Коли, нарешті, все було готово до стартів, вияснилось, что дощ розмив всі стоячі місця на арені для змагань. Організатори потерпіли колосальні збитки, вони були змушені продавати квитки лише у перший ряд місць – єдиний ряд сидячих місць.
У день змагань кожен з N глядачів, які придбали квитки у перший ряд, зайняв одне з місць у першому ряду. Проте при перевірці квитків вияснилось, що жоден з глядачів не сидить на своєму місці, і при цьому всі місця зайняті. За один крок волонтер може поміняти місцями двох сусідніх глядачів, якщо обидва сидять не на своїх місцях. Якщо ж глядач вже сидить на своєму місці, чіпати його не можна, це заважає йому спостерігати змагання. Вам необхідно допомогти знайти схему пересадки, яка розсажує всіх глядачів на свої місця. Покваптесь, адже незабаром почнуться самі цікаві виступи.
Вхідні дані
У першому рядку записано ціле число N (2 ≤ N ≤ 300). У другому рядку записано N чисел – перестановки від 1 до N – початкове розміщення глядачів. Гарантується, що ніхто з глядачів на початку не сидить на своєму місці.
Вихідні дані
Якщо розв'язку не існує, необхідно вивести -1. Інакше у першому рядку вивести число кроків у схемі пересадки. Далі вивести схему пересадки, кожен крок у окремому рядку. Крок описується двома числами – місцями, гдядачі на яких міняються місцями на цьому кроці. Кількість кроків не повинна перевищувати 45000. Якщо існує декілька розв'язків, вивести довільний.