To jest zadanie interaktywne.

Wierzymy, że nie widzieliście CZL od kilku miesięcy, ale on powraca! Udało nam się umieścić małego U, małego Z oraz CZL w jednym zestawie zadań.

CZL posiada potasowaną talię kart. Talia składa się z $n$ kart ułożonych od góry do dołu (pozycje kart są numerowane od $0$ do $n-1$). Wartości kart to liczby ze zbioru $\{0, 1, 2, \dots, n-1\}$, przy czym każda wartość występuje dokładnie raz. Twoim zadaniem jest odgadnięcie wartości każdej karty w talii, ale wielki magik nie zdradzi ci ich tak po prostu.

Na początku lewa i prawa ręka CZL znajdują się na pozycji karty $0$. W każdym ruchu możesz nakazać mu przesunięcie lewej ręki o jedną kartę w górę lub w dół. Możesz również nakazać mu przesunięcie prawej ręki o jedną kartę w górę lub w dół. Możesz także zapytać, czy karta pod lewą ręką jest mniejsza od karty pod prawą ręką. Dzięki tym operacjom musisz ustalić wartość każdej karty w talii, od góry do dołu.

Choć ręce CZL są bardzo sprawne, musi on jeszcze wykonywać sztuczki dla innych osób. Dlatego prosimy, abyś ustalił wartości wszystkich kart, wykonując nie więcej niż $7,0 \cdot 10^8$ ruchów.

Twój kod musi zawierać nagłówek "lancllords.h". Musisz zaimplementować funkcję:

vector<int> answer(int n);

W tej funkcji liczba całkowita $n$ oznacza liczbę kart. Funkcja powinna zwrócić tablicę $P$ o długości $n$, gdzie P[i] oznacza wartość karty na $i$-tej pozycji od góry.

Zakładamy, że lewa ręka CZL znajduje się na pozycji $p$, a prawa na pozycji $q$. Możesz wywoływać następujące funkcje:

void inc_p();

Przesuwa lewą rękę CZL o jedną kartę w dół.

void dec_p();

Przesuwa lewą rękę CZL o jedną kartę w górę.

void inc_q();

Przesuwa prawą rękę CZL o jedną kartę w dół.

void dec_q();

Przesuwa prawą rękę CZL o jedną kartę w górę.

bool cmp();

Porównuje wartość karty na pozycji $p$ z wartością karty na pozycji $q$. Zwraca true, jeśli karta na pozycji $p$ jest mniejsza od karty na pozycji $q$, w przeciwnym razie zwraca false.

Za każdym razem, gdy wywołasz jedną z pierwszych czterech funkcji, zmienna cnt w graderze zwiększy się o $1$. Podczas końcowej oceny, jeśli wartość cnt będzie zbyt duża, test zostanie uznany za niezaliczony. Musisz zawsze dbać o to, aby $0 \le p, q < n$, w przeciwnym razie test również zostanie uznany za niezaliczony.

Pamiętaj, że biblioteka interakcyjna działa w czasie nieprzekraczającym pięciu sekund, pod warunkiem, że liczba wywołań pierwszych czterech funkcji nie przekracza $7,0 \cdot 10^8$, a liczba wywołań piątej funkcji nie przekracza $10^7$. Oznacza to, że Twój kod ma co najmniej pięć sekund czasu wykonania.

Dostarczamy pliki grader.cpp oraz lancllords_sample.cpp, gdzie lancllords_sample.cpp jest przykładowym rozwiązaniem. Możesz przetestować swój program za pomocą polecenia g++ lancllords.cpp grader.cpp -o lancllords -O2.

Wejście

W pierwszej linii znajduje się liczba całkowita $n$, oznaczająca liczbę kart.

W kolejnej linii znajduje się $n$ liczb $P_0, \dots, P_{n-1}$, oznaczających wartości kart od góry do dołu.

Wyjście

Informacje są wyprowadzane przez bibliotekę interakcyjną. Podczas testów lokalnych, jeśli wartości $p$ lub $q$ wyjdą poza zakres, zostanie wypisane "Out of bound!". Jeśli zwrócisz błędną odpowiedź, zostanie wypisane "Wrong answer!", w przeciwnym razie zostanie wypisane "Right Output!" oraz w kolejnej linii liczba wywołań pierwszych czterech funkcji.

Biblioteka interakcyjna dostarczona w plikach różni się od tej używanej w finalnej ocenie! Jednak w finalnym systemie testującym permutacja jest generowana z góry i nie zmienia się w zależności od Twoich zapytań.

Przykład

Przykład 1 Wejście

5
3 4 0 1 2

Przykład 1 Wyjście

Right Output!
You use 100 operations!

Uwagi

Ten przykład oznacza, że wywołałeś pierwsze cztery funkcje 100 razy i uzyskałeś poprawną permutację.

Przykład 2

Patrz dostarczone pliki.

Przykład 3

Patrz dostarczone pliki.

Podzadania

Dla wszystkich danych $1 \le n \le 150000$.

Podzadanie $1$ ($6$ pkt): $n \le 1000$

Podzadanie $2$ ($7$ pkt): $n \le 10000$

Podzadanie $3$ ($38$ pkt): $n \le 30000$

Podzadanie $4$ ($25$ pkt): $n \le 50000$

Podzadanie $5$ ($24$ pkt): $n \le 150000$