У Козака Вуса суцільні двійки з інформатики... Ні, не тому що він погано володіє комп'ютером. Просто віднедавна усі завдання слід виконувати на спеціальному автоматі, який дуже полюбляє степені двійки.
Степінь двійки — число вигляду 2x, де x — ціле невід'ємне число. Наприклад, числа 1,2,4,8,16 — степені двійки, а ось 3,7,10,15,19 — ні.
Автомат оперує масивом цілих чисел a довжини n, причому n — степінь двійки. Усе, що вміє автомат, — переставити число з t-ої позиції на початок масиву, зсунувши при цьому всі числа, що стоять від початку до цієї позиції. Наприклад, якщо a=[1,2,3,4,5,6,7,8] і ми переставляємо 4-ий елемент на початок, отримаємо a=[4,1,2,3,5,6,7,8]. Зверніть увагу, що автомат уміє виконувати цю операцію лише для t, що є степенем двійки.
Вус зі всіх сил намагається виконати останнє домашнє завдання — для заданого масиву написати послідовність t1,t2,…,tk, яка б перетворила масив на відсортований за неспаданням. Щось йому вдається, але він просить Вас зробити те саме, щоб звірити відповіді. Допоможіть йому, знайшовши таку послідовність!
Перший рядок містить два цілі числа n та g (2≤n≤128, 0≤g≤6) — довжина масиву та номер блоку. Гарантується, що n — степінь двійки.
Наступний рядок містить рівно n цілих чисел a1,a2,…,an (1≤ai≤n) — елементи масиву.
У першому рядку виведіть одне ціле число k (0≤k≤16384) — кількість команд.
У другому рядку виведіть k цілих чисел t1,t2,…,tk (1≤ti≤n) — послідовність команд, що сортує масив. Таких послідовностей може бути багато, тому виведіть будь-яку (не обов'язково найменшої довжини).
У першому прикладі масив був [4,3,2,1]. Після перестановки другого елемента отримаємо [3,4,2,1]. Далі двічі переставляємо останній елемент, отримуючи спочатку [1,3,4,2], а потім [2,1,3,4]. Останнім ходом переставляємо другий елемент на перше місце, отримуючи [1,2,3,4] — відсортований за неспаданням масив.
У другому прикладі масив був [1,3,1,2]. Після перестановки четвертого елемента отримаємо [2,1,3,1]. Далі переставляємо другий елемент, отримуючи [1,2,3,1]. Укінці переставляємо останній елемент, отримуючи [1,1,3,4] — упорядкований масив.
(11 балів) n=2; усі числа різні;
(15 балів) n=4; усі числа різні;
(20 балів) n=8; усі числа різні;
(22 бали) рівно 2n чисел масиву — одиниці, усі інші — двійки;
(23 бали) усі числа різні;
(9 балів) без додаткових обмежень.