Сноубординг
Погода в первые дни олимпиады не радовала ни спортсменов, ни зрителей. Но вот кому пришлось действительно тяжело, так это организаторам. Проливной дождь и теплые дни уничтожили большую часть снега на трассе для сноуборда. Из-за этого организаторы были вынуждены несколько раз переносить соревнования, пытаясь восстановить трассу с помощью запасенного снега.
Когда, наконец, все было готово к стартам, выяснилось, что дождь размыл все стоячие места на арене для соревнований. Организаторы понесли колоссальные убытки, они были вынуждены продавать билеты только в первый ряд мест – единственный ряд сидячих мест.
В день соревнований каждый из N зрителей, купивших билеты в первый ряд, занял одно из мест в первом ряду. Однако при проверке билетов выяснилось, что ни один из зрителей не сидит на своем месте, и при этом все места заняты. За один шаг волонтер может поменять местами двух соседних зрителей, если оба сидят не на своих местах. Если зритель уже сидит на своем месте, трогать его нельзя, это мешает ему смотреть соревнования. Вам необходимо помочь найти схему пересадки, рассаживающую всех зрителей на свои места. Поторопитесь, ведь скоро начнутся самые интересные выступления.
Входные данные
В первой строке записано целое число N (2 ≤ N ≤ 300). Во второй строке записано N чисел – перестановка от 1 до N – начальное расположение зрителей. Гарантируется, что никакой из зрителей изначально не сидит на своем месте.
Выходные данные
Если решения не существует, необходимо вывести -1. Иначе в первой строке вывести число шагов в схеме пересадки. Далее вывести схему пересадки, каждый шаг в отдельной строке. Шаг описывается двумя числами – местами, зрители на которых меняются местами на этом шаге. Количество шагов не должно превышать 45000. Если существует несколько решений, вывести любое.