Po kilkuset latach miasto JOI popadło w ruinę. Badaczka IOI-chan eksploruje teraz obszar, na którym znajdowała się biblioteka. Na podstawie wyników badań wiadomo, co następuje:

• W bibliotece miasta JOI znajdowała się pozioma półka na książki. Miała ona $N$ miejsc ustawionych w rzędzie i ponumerowanych od lewej do prawej od $0$ do $N-1$. Na każdym miejscu można było umieścić dokładnie jedną książkę.
• Na półce znajdowało się $N$ książek, ponumerowanych od $0$ do $N-1$.
• Ustawienie książek to sposób rozmieszczenia wszystkich $N$ książek na $N$ miejscach.
• Istniało poprawne ustawienie książek, w którym na miejscu $i$ znajdowała się książka $B_i$ ($0 \le i \le N-1$). Wszystkie wartości $B_i$ były różne.

Ustawienie książek często się zmienia. Wiemy, że w tej bibliotece przywracano poprawne ustawienie, powtarzając poniższą operację.

Operacja: Niech książka $x$ będzie najbardziej wysuniętą na lewo spośród książek, których miejsce różni się od ich miejsca w poprawnym ustawieniu. Niech książka $y$ będzie książką znajdującą się obecnie na miejscu, na którym w poprawnym ustawieniu znajduje się książka $x$. Zamień miejscami książki $x$ i $y$.

Choć IOI-chan odnalazła stare książki z biblioteki, nie udało jej się ustalić poprawnego ustawienia. Znalazła jednak starą maszynę, która zarządzała operacjami na półce w bibliotece. Jeśli określimy ustawienie $N$ książek i wyślemy do maszyny zapytanie, odpowie ona, ile operacji potrzeba, aby przywrócić poprawne ustawienie wszystkich książek. IOI-chan chce poznać poprawne ustawienie, wysyłając zapytania do maszyny. Ponieważ maszyna jest stara, może wysłać do niej najwyżej $5\,000$ zapytań.

Napisz program, który na podstawie informacji o półce ustali poprawne ustawienie książek, wysyłając najwyżej $5\,000$ zapytań.

Szczegóły implementacji

Należy przesłać jeden plik.

Plik ten to library3.cpp. Powinien implementować poniższą funkcję. Program powinien dołączyć library3.h za pomocą dyrektywy preprocesora #include.

void solve(int N)

Ta funkcja jest wywoływana tylko raz dla każdego przypadku testowego.

• Parametr N oznacza liczbę książek $N$.

W pliku library3.cpp można wywoływać poniższe funkcje.

int query(const std::vector<int> a)

Za pomocą tej funkcji IOI-chan wysyła zapytanie do maszyny.

• Parametr a jest tablicą długości $N$ i określa ustawienie $N$ książek podane w zapytaniu. W tym ustawieniu książka a[i] ($0 \le i \le N-1$) ma znajdować się na miejscu $i$.
• Zwracana wartość to liczba operacji potrzebnych do przywrócenia poprawnego ustawienia wszystkich książek, zaczynając od podanego ustawienia.
• Długość parametru a musi wynosić $N$. Niespełnienie tego warunku skutkuje werdyktem Błędna odpowiedź [1].
• Każdy element parametru a musi należeć do przedziału od $0$ do $N-1$. Niespełnienie tego warunku skutkuje werdyktem Błędna odpowiedź [2].
• Każdy element parametru a musi różnić się od wszystkich pozostałych. Niespełnienie tego warunku skutkuje werdyktem Błędna odpowiedź [3].
• Nie wolno wywołać funkcji query więcej niż $5\,000$ razy. Jeśli zostanie wywołana więcej niż $5\,000$ razy, program otrzyma werdykt Błędna odpowiedź [4].

void answer(std::vector<int> b)

Wywołując tę funkcję, program podaje poprawne ustawienie książek.

• Parametr b jest tablicą długości $N$ i określa ustawienie $N$ książek podane w odpowiedzi. W tym ustawieniu książka b[i] ($0 \le i \le N-1$) ma znajdować się na miejscu $i$.
• Długość parametru b musi wynosić $N$. Niespełnienie tego warunku skutkuje werdyktem Błędna odpowiedź [5].
• Każdy element parametru b musi należeć do przedziału od $0$ do $N-1$. Niespełnienie tego warunku skutkuje werdyktem Błędna odpowiedź [6].
• Każdy element parametru b musi różnić się od wszystkich pozostałych. Niespełnienie tego warunku skutkuje werdyktem Błędna odpowiedź [7].
• Podane ustawienie musi być poprawnym ustawieniem. Niespełnienie tego warunku skutkuje werdyktem Błędna odpowiedź [8].
• Funkcję answer należy wywołać dokładnie raz. Jeśli zostanie wywołana więcej niż raz, program otrzyma werdykt Błędna odpowiedź [9]. Jeśli funkcja solve zakończy działanie bez wywołania funkcji answer, program otrzyma werdykt Błędna odpowiedź [10].

Ważne uwagi

• Program może implementować inne funkcje do użytku wewnętrznego oraz korzystać ze zmiennych globalnych.
• Program nie może korzystać ze standardowego wejścia ani standardowego wyjścia. Nie może też w żaden sposób komunikować się z innymi plikami. Może jednak wypisywać informacje do debugowania na standardowe wyjście błędów.

Kompilacja i uruchomienie testowe

Ze strony konkursu można pobrać archiwum zawierające przykładowy program oceniający służący do testowania programu. Archiwum zawiera również przykładowy plik źródłowy twojego programu.

Przykładowy program oceniający znajduje się w pliku grader.cpp. Aby przetestować program, umieść grader.cpp, library3.cpp i library3.h w tym samym katalogu i skompiluj je poniższym poleceniem. Zamiast tego można uruchomić skrypt compile.sh zawarty w archiwum.

g++ -std=gnu++20 -O2 -o grader grader.cpp library3.cpp

Po udanej kompilacji powstanie plik wykonywalny grader.

Zwróć uwagę, że rzeczywisty program oceniający różni się od przykładowego. Przykładowy program oceniający działa jako jeden proces, który odczytuje dane ze standardowego wejścia i wypisuje wyniki na standardowe wyjście.

Wejście przykładowego programu oceniającego

Przykładowy program oceniający odczytuje następujące dane ze standardowego wejścia.

$$ \begin{gathered} N\\ B_0\ B_1\ \cdots\ B_{N-1} \end{gathered} $$

$B_i$ ($0 \le i \le N-1$) to numer książki znajdującej się na miejscu $i$ w poprawnym ustawieniu.

Wyjście przykładowego programu oceniającego

Przykładowy program oceniający wypisuje poniższe informacje na standardowe wyjście i standardowe wyjście błędów (cudzysłowy podano dla jasności).

• Jeśli program zostanie uznany za poprawny, podaje liczbę wywołań query w postaci Accepted: 3000.
• Jeśli program otrzyma dowolny rodzaj werdyktu błędnej odpowiedzi, przykładowy program oceniający wypisuje jego typ, na przykład Wrong Answer [3].

Jeśli program spełnia warunki kilku rodzajów błędnej odpowiedzi, przykładowy program oceniający zgłasza tylko jeden z nich.

Ograniczenia

Wszystkie dane wejściowe spełniają poniższe warunki.

• $2 \le N \le 500$.
• $0 \le B_i \le N-1$ ($0 \le i \le N-1$).
• $B_i \ne B_j$ ($0 \le i<j \le N-1$).
• Wszystkie podane wartości są liczbami całkowitymi.

Podzadania

1. (2 punkty) $N \le 6$.
2. (19 punktów) $N \le 100$.
3. (79 punktów) Brak dodatkowych ograniczeń.

Przykład interakcji

Poniżej podano przykładowe wejście dla przykładowego programu oceniającego i odpowiadające mu wywołania funkcji.

Wejście 1

4
2 0 3 1

Przykładowe wywołania funkcji

Na przykład wywołanie query([0, 1, 2, 3]) określa ustawienie, w którym książki $0,1,2,3$ znajdują się odpowiednio na miejscach $0,1,2,3$. Operacja jest powtarzana następująco.

1. Zamień miejscami książki $0$ i $1$. Książki $1,0,2,3$ znajdują się odpowiednio na miejscach $0,1,2,3$.
2. Zamień miejscami książki $1$ i $3$. Książki $3,0,2,1$ znajdują się odpowiednio na miejscach $0,1,2,3$.
3. Zamień miejscami książki $3$ i $2$. Książki $2,0,3,1$ znajdują się odpowiednio na miejscach $0,1,2,3$.

Ponieważ przywrócenie poprawnego ustawienia wszystkich książek wymaga 3 operacji, zwracana wartość wynosi 3.

To przykładowe wejście spełnia ograniczenia wszystkich podzadań.