Луноход наконец-то достиг поверхности планеты X. Приземлившись, он встретился с препятствием, на котором записана перестановка \(p\) длины \(n\). Учёным удалось выяснить, что для того, чтобы преодолеть препятствие, необходимо добиться того, чтобы \(p\) стала тождественной (должно выполняться \(p_i = i\) для всех \(i\)).
К сожалению, учёные не могут управлять роботом на расстоянии. Из-за этого единственный способ сделать \(p\) тождественной — применить к \(p\) следующую операцию несколько раз:
- Выбрать две позиции \(i\) и \(j\) (\(i \neq j\)), такие, что \(p_j = i\) и поменять местами значения \(p_i\) и \(p_j\). Операция занимает \((j - i)^2\) секунд из-за выполнения её роботом.
Позиции \(i\) и \(j\) выбирает робот (учёные не могут влиять на его выбор). Он будет применять эту операцию до тех пор, пока \(p\) не станет тождественной. Можно показать, что не более чем через \(n\) операций (вне зависимости от выбора \(i\) и \(j\)) перестановка станет тождественной.
Учёные попросили Вас найти максимальное время, за которое робот сделает \(p\) тождественной (т.е. худший возможный вариант развития событий), чтобы они могли отдохнуть или же отправить более продвинутый луноход на планету X. Также учёные попросили Вас предоставить пример перестановки \(p\) и последовательности операций робота, которые максимизируют ответ.
Для лучшего понимания условия обратитесь к примечаниям к примеру.
Выходные данные
Для каждого набора входных данных, в первой строке выведите максимальное время работы робота (в секундах).
Во второй строке выведите исходную перестановку \(p\), на которой достигается Ваш ответ.
В третьей строке выведите количество операций \(m \leq n\), которое робот сделает в Вашем примере.
В следующих \(m\) строках выведите по два числа \(i\) и \(j\) — индексы позиций, которые робот выбирает на этой операции. Обратите внимание, что \(p_j = i\) должно выполняться (в момент операции).
Примечание
Для \(n = 2\), \(p\) может быть равна \([1, 2]\) или \([2, 1]\). В первом случае \(p\) уже является тождественной, а во втором случае робот сделает её тождественной за \(1\) секунду вне зависимости от выбора \(i\) и \(j\) на первой операции.
Для \(n = 3\), \(p\) может оказаться равна \([2, 3, 1]\).
- Если робот выберет \(i = 3, j = 2\) на первой операции, то через одну секунду \(p\) станет равна \([2, 1, 3]\). Теперь робот может выбрать только \(i = 1, j = 2\) или \(i = 2, j = 1\). В любом из этих случаев, \(p\) станет тождественной через ещё одну секунду (всего — \(2\) секунды).
- Если робот выберет \(i = 1, j = 3\) на первой операции, то через четыре секунды \(p\) станет равна \([1, 3, 2]\). Вне зависимости от выбора \(i\) и \(j\) на второй операции, \(p\) станет тождественной через пять секунд работы робота.
Можно показать, что робот всегда сможет завершить работу с перестановкой длины \(3\) за \(5\) или меньше секунд.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
3
3
|
1
2 1
1
2 1
5
2 3 1
2
1 3
3 2
5
2 3 1
2
1 3
2 3
|