Двійкові маніпуляції

У Козака Вуса суцільні двійки з інформатики... Ні, не тому що він погано володіє комп'ютером. Просто віднедавна усі завдання слід виконувати на спеціальному автоматі, який дуже полюбляє степені двійки.

Степінь двійки — число вигляду $2^x$, де $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$, що є степенем двійки.

Вус зі всіх сил намагається виконати останнє домашнє завдання — для заданого масиву написати послідовність $t_1,t_2,\dots ,t_k$, яка б перетворила масив на відсортований за неспаданням. Щось йому вдається, але він просить Вас зробити те саме, щоб звірити відповіді. Допоможіть йому, знайшовши таку послідовність!

Giriş verilənləri

Перший рядок містить два цілі числа $n$ та $g$ ($2\le n\le 128$, $0\le g\le 6$) — довжина масиву та номер блоку. Гарантується, що $n$ — степінь двійки.

Наступний рядок містить рівно $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le n$) — елементи масиву.

Çıxış verilənləri

У першому рядку виведіть одне ціле число $k$ ($0\le k\le 16384$) — кількість команд.

У другому рядку виведіть $k$ цілих чисел $t_1,t_2,\dots ,t_k$ ($1\le t_i\le n$) — послідовність команд, що сортує масив. Таких послідовностей може бути багато, тому виведіть будь-яку (не обов'язково найменшої довжини).

Nümunələr

Qeyd

У першому прикладі масив був $[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]$ — упорядкований масив.

Qiymətləndirmə

1. ($11$ балів) $n=2$; усі числа різні;

2. ($15$ балів) $n=4$; усі числа різні;

3. ($20$ балів) $n=8$; усі числа різні;

4. ($22$ бали) рівно $\frac{n}{2}$ чисел масиву — одиниці, усі інші — двійки;

5. ($23$ бали) усі числа різні;

6. ($9$ балів) без додаткових обмежень.