Екзамен в Нічну Варту#12424

Екзамен в Нічну Варту

2 секунди

256 мегабайтів

Складна

Ще з часів Андалів та перших людей у Вестеросі була відома функція $f (p)$ , де p — перестановка довільної довжини. Вона визначається наступним чином.

Визначимо масив $d$ наступним чином. $d_{i} = ∣ p_{i} - p_{i + 1} ∣$ d_i = |p_i-p_{i+1}| для всіх $1 \leq i \leq m - 1$ 1 \le i \le m-1,де $m$ — довжина перестановки. Тоді $f (p)$ дорівнює кількості індексів $1 \leq i \leq m - 2$ 1 \le i \le m-2 таких,що $d_{i} \neq \equiv d_{i + 1} (mod 2)$ d_i \not\equiv d_{i+1} \pmod{2}.

Джон Сноу з дитинства мріє потрапити до Нічної Варти і тому збирається здавати екзамен. Його суть полягає в знаходженні перестановки довжини $n$ з максимальним значенням $f (p)$ . Проте екзаменатор Сер Аллісерн Торн ненавидить Джона Сноу і тому вимагає від нього,щоб його перестановка була лексикографічно мінімальною серед усіх,які дають максимальне значення $f (p)$ .

Так як Джон Сноу нічого не знає він потребує вашої допомоги. Будь ласка,допожіть йому здати екзамен в Нічну Варту.

Вхідні дані

Перший рядок містить ціле число $n$ ( $3 \leq n \leq 2 \cdot 1 0^{5}$ 3 \le n \le 2 \cdot 10^5) — довжина перестановки.

Вихідні дані

Виведіть лексикографічно мінімальну перестановку з максимальним значенням $f (p)$ .

Приклади

Приклад 1

Приклад 2

Примітка

До другого тесту:

Масив $d$ буде мати вигляд: $1, 0, 1, 0, 1$ {1,0,1,0,1}.

Отже шукане значення $f (p)$ дорівнює $4$ .

Оскільки $m - 2$ m-2 $=$ $4$ то $4$ це максимально можливе значення $f (p)$ .

Оцінювання

Підзадача $1$ ( $15$ балів) : $(n \leq 10)$ (n\le 10)
Підзадача $2$ ( $25$ балів) : $(n \leq 100)$ (n\le 100)
Підзадача $3$ ( $60$ балів) : $(n \leq 1000)$ (n\le 1000)
Підзадача $4$ ( $100$ балів) : Без додаткових обмежень