Компания ADM представила новый квантовый процессор. Благодаря нему очень быстро можно применять функцию «tripleswap» к некоторому массиву a.
tripleswap(i, j, k, x, y, z) — переставляет элемент, который стоит на позиции i на позицию x, элемент с позиции j на позицию y и элемент с позиции k на позицию z. При этом i, j, k, x, y и z — корректные индексы массива, множество {i,j,k} совпадает с множеством {x,y,z}, а также выполняется условие, что i, j, k различны между собой и x, y, z различны между собой.
Таким, образом, пусть есть массив, содержащий первую перестановку из пяти элементов [1,2,3,4,5]. Если применить к нему tripleswap(1, 5, 4, 5, 1, 4) получится массив [5,2,3,4,1]. При этом, выполнить tripleswap(1, 5, 4, 5, 2, 4) или tripleswap(1, 5, 1, 5, 1, 1) нельзя, так как такие наборы аргументов считаются некорректными.
Вас пригласили протестировать возможности нового процессора. Для первого теста вам дана перестановка из n чисел, нужно отсортировать ее по возрастанию при помощи функции tripleswap, вызвав данную функцию не более, чем n/2 раз (деление целочисленное, 5/2=2).
Входные данные
В первой строке дано одно натуральное число n — размер перестановки (3≤n≤100).
Во второй строке заданы n чисел ai — элементы перестановки (1≤ai≤n). Гарантируется, что все ai попарно различны.
Выходные данные
В первой строке выведите одно число m — число вызов функции tripleswap, которые сортируют данную перестановку требуемым способом.
В каждой из следующих m строк выведите по шесть чисел — аргументы для каждого вызова функции.
Если есть несколько решений, разрешается вывести любое.
| Ввод |
Вывод |
5
1 2 3 4 5 |
0 |
5
5 4 3 2 1 |
2
2 4 5 4 5 2
1 2 5 5 1 2 |
Примечание
В первом тесте последовательность уже отсортирована, поэтому потребуется ноль вызовов данной функции. Во втором тесте изменение элементов массива будет выглядеть следующим образом: [5,4,3,2,1]⇒[5,1,3,4,2]⇒[1,2,3,4,5].