F. XOR-разворот циклического массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a_0, a_1, \ldots, a_{n-1}$$$ длины $$$n$$$. Изначально $$$a_i = 2^i$$$ для всех $$$0 \le i \lt n$$$. Обратите внимание, что элементы массива $$$a$$$ нумеруются с нуля.

Вы хотите развернуть этот массив (то есть сделать $$$a_i$$$ равным $$$2^{n-1-i}$$$ для всех $$$0 \le i \lt n$$$). Чтобы сделать это, вы можете сделать следующую операцию не более $$$250\,000$$$ раз:

  • Выбрать целое число $$$i$$$ ($$$0 \le i \lt n$$$) и заменить $$$a_i$$$ на $$$a_i \oplus a_{(i+1)\bmod n}$$$.

Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Найдите любую последовательность операций, после выполнения которой массив $$$a$$$ окажется развёрнутым. Можно показать, что при данных ограничениях решение всегда существует.

Входные данные

В первой строке дано одно число $$$n$$$ ($$$2 \le n \le 400$$$) — длина массива $$$a$$$.

Выходные данные

В первой строке выведите одно число $$$k$$$ ($$$0 \le k \le 250\,000$$$) — количество использованных операций.

Во второй строке выведите $$$k$$$ чисел $$$i_1,i_2,\ldots,i_k$$$ ($$$0 \le i_j \lt n$$$), которые обозначают, что на $$$j$$$-й операции вы выбрали число $$$i_j$$$.

Обратите внимание, что вам не требуется минимизировать количество операций.

Примеры
Входные данные
2
Выходные данные
3
1 0 1
Входные данные
3
Выходные данные
9
1 0 1 0 2 1 0 1 0
Примечание

В примечании красным выделены элементы, находящиеся в позициях, к которым применяются операции.

В первом наборе входных данных массив $$$a$$$ изменится следующим образом:

$$$[1,\color{red}{2}] \rightarrow [\color{red}{1},3] \rightarrow [2,\color{red}{3}] \rightarrow [2,1]$$$.

Во втором наборе входных данных массив $$$a$$$ изменится следующим образом:

$$$[1,\color{red}{2},4] \rightarrow [\color{red}{1},6,4] \rightarrow [7,\color{red}{6},4] \rightarrow [\color{red}{7},2,4] \rightarrow [5,2,\color{red}{4}] \rightarrow [5,\color{red}{2},1] \rightarrow [\color{red}{5},3,1] \rightarrow [6,\color{red}{3},1] \rightarrow [\color{red}{6},2,1] \rightarrow [4,2,1]$$$.