Хаотична перестановка
Сьогодні Васю заставили прибирати у класі. Втомившись наводити порядок, він вирішив, що тепер він просто повинен у якості компенсації влаштувати де-небудь хаос. І тут йому на очі потрапила написана учителем на дошці перестановка чисел від 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). Відповідь, запропонована у другому прикладі, також коректна. У третьому прикладі перестановка вже хаотична і нічого змінювати не потрібно.