Хаотическая перестановка
Сегодня Васю заставили убираться в классе. Устав наводить порядок, он решил, что теперь он просто должен в качестве компенсации устроить где-нибудь хаос. И тут ему на глаза попалась написанная учителем на доске перестановка чисел от 1 до n. Напомним, что перестановкой чисел от 1 до n называется последовательность из n чисел, в которой каждое из них встречается ровно один раз.
Вася считает, что три подряд идущих элемента находятся в порядке, если они упорядочены либо по возрастанию, либо по убыванию. Он называет перестановку хаотической, если никакая тройка подряд идущих элементов не находится в порядке.
Вася решил изменить перестановку на доске, сделав её хаотической. Для этого он решил не более n раз поменять местами два соседних элемента в перестановке.
Помогите Васе сделать перестановку хаотической, пока не пришел учитель и не наказал его за то, что он занимается ерундой вместо уборки.
Входные данные
На доске написана исходная перестановка. Первая строка содержит длину перестановки n (3 ≤ n ≤ 1000). Вторая строка содержит n различных целых чисел, каждое из которых лежит в диапазоне от 1 до n - саму перестановку.
Выходные данные
В первой строке выведите количество операций k, которое необходимо сделать Васе. В следующей строке выведите k чисел - саму последовательность операций. Если на очередном шаге надо поменять местами i-ый и i + 1-ый элементы перестановки, необходимо вывести число i.
Если ответов несколько, вы можете вывести любой. Обратите внимание, что вам не обязательно минимизировать количество операций. Достаточно, чтобы оно было не больше, чем n. Если решения не существует, выведите число -1.
Пояснение к примерам
В первом примере перестановка будет иметь вид (1 2 3 4 5) → (1 2 3 5 4) → (2 1 3 5 4) → (2 3 1 5 4). Ответ, предложенный во втором примере, тоже корректен. В третьем примере перестановка уже хаотическая, и ничего менять не надо.