Это интерактивная задача.

Вы наверняка не видели CZL уже несколько месяцев, и вот он вернулся! Нам удалось собрать персонажей Сяо У, Сяо Z и CZL в одном наборе задач.

У CZL есть колода перемешанных карт, состоящая из $n$ карт, расположенных сверху вниз (позиции карт нумеруются от $0$ до $n-1$). Значения карт представляют собой перестановку чисел $0, 1, 2, \dots, n-1$. Вам нужно определить значение каждой карты в колоде. Но как великий фокусник может просто взять и рассказать вам всё?

Изначально левая и правая руки CZL находятся на позиции $0$-й карты. Вы можете отдавать команды перемещать его левую руку на одну карту вверх или вниз, а также перемещать правую руку на одну карту вверх или вниз. Вы также можете попросить его сравнить, является ли карта под левой рукой меньше карты под правой рукой. С помощью этих операций вам необходимо определить значение каждой карты в колоде сверху вниз.

Хотя руки CZL очень ловкие, ему нужно показывать фокусы другим людям. Поэтому, пожалуйста, определите значения всех карт, совершив не более $7.0 \cdot 10^8$ перемещений.

Ваш код должен содержать заголовочный файл "lancllords.h", и вам необходимо реализовать функцию:

vector<int> answer(int n);

В этой функции целое число $n$ обозначает количество карт. Функция должна вернуть массив $P$ длины $n$, где P[i] — значение $i$-й карты сверху.

Предположим, что левая рука CZL находится на позиции $p$, а правая — на позиции $q$. Вы можете вызывать следующие функции:

void inc_p();

Перемещает левую руку CZL на одну карту вниз.

void dec_p();

Перемещает левую руку CZL на одну карту вверх.

void inc_q();

Перемещает правую руку CZL на одну карту вниз.

void dec_q();

Перемещает правую руку CZL на одну карту вверх.

bool cmp();

Сравнивает значения карт на позициях $p$ и $q$. Если карта на позиции $p$ меньше карты на позиции $q$, возвращает true, иначе — false.

За каждый вызов первых четырех функций переменная cnt в интеракторе увеличивается на $1$. Если в процессе тестирования значение cnt окажется слишком большим, тест будет считаться не пройденным. Вы должны всегда гарантировать, что $0 \le p, q < n$, в противном случае тест также будет считаться не пройденным.

Обратите внимание, что интерактивная библиотека работает не более пяти секунд при условии, что количество вызовов первых четырех функций не превышает $7.0 \cdot 10^8$, а количество вызовов пятой функции не превышает $10^7$. Это означает, что у вашего кода есть как минимум пять секунд времени выполнения.

Мы предоставляем файлы grader.cpp и lancllords_sample.cpp, где lancllords_sample.cpp является примером кода участника. Вы можете протестировать свою программу с помощью команды g++ lancllords.cpp grader.cpp -o lancllords -O2.

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

Первая строка содержит целое число $n$, количество карт.

Следующая строка содержит $n$ чисел $P_0, \dots, P_{n-1}$, представляющих значения карт сверху вниз.

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

Вывод осуществляется интерактивной библиотекой. При локальном тестировании, если значения $p$ или $q$ выходят за границы, будет выведено "Out of bound!". Если возвращенный вами ответ неверен, будет выведено "Wrong answer!", в противном случае будет выведено "Right Output!" и количество вызовов первых четырех функций.

Интерактивная библиотека, которую мы предоставляем, отличается от той, что будет использоваться при финальном тестировании! Однако в финальной системе перестановка также генерируется заранее и не меняется в зависимости от ваших запросов.

Примеры

Пример 1 Входные данные

5
3 4 0 1 2

Пример 1 Выходные данные

Right Output!
You use 100 operations!

Примечание к примеру 1

Этот пример означает, что вы использовали $100$ операций вызова первых четырех функций и получили верную перестановку.

Пример 2

См. предоставленные файлы.

Пример 3

См. предоставленные файлы.

Подзадачи

Для всех данных $1 \le n \le 150000$.

Подзадача $1$ ($6$ баллов): $n \le 1000$

Подзадача $2$ ($7$ баллов): $n \le 10000$

Подзадача $3$ ($38$ баллов): $n \le 30000$

Подзадача $4$ ($25$ баллов): $n \le 50000$

Подзадача $5$ ($24$ балла): $n \le 150000$