Минуло кілька сотень років, і місто JOI перетворилося на руїни. Дослідниця IOI-chan зараз досліджує місце, де була побудована бібліотека. За результатами дослідження відомо таке:

• У бібліотеці міста JOI була горизонтальна книжкова полиця. На ній було $N$ місць для книжок, розташованих в один ряд і пронумерованих від $0$ до $N-1$ зліва направо. На кожному місці могла стояти рівно одна книжка.
• На полиці було $N$ книжок. Ці $N$ книжок були пронумеровані від $0$ до $N-1$.
• Розташування книжок — це спосіб розмістити всі $N$ книжок на $N$ місцях.
• Існувало правильне розташування книжок, у якому на місці $i$ стояла книжка $B_i$ ($0 \le i \le N-1$). Усі $B_i$ різні.

Розташування книжок часто змінюється. Відомо, що в цій бібліотеці книжки повертали до правильного розташування, повторюючи таку операцію.

Операція. Нехай книжка $x$ — найлівіша серед книжок, чиє місце відрізняється від місця у правильному розташуванні. Також нехай книжка $y$ — книжка, що в поточному розташуванні стоїть на тому місці, де у правильному розташуванні стоїть книжка $x$. Поміняти місцями книжки $x$ і $y$.

Хоча IOI-chan знайшла старі книжки бібліотеки, вона не змогла з'ясувати правильне розташування. Проте вона знайшла стару машину, яка керувала операціями над книжковою полицею бібліотеки. Якщо вказати розташування $N$ книжок і надіслати запит машині, вона повідомить кількість операцій, потрібних, щоб повернути всі книжки до правильного розташування. IOI-chan хоче дізнатися правильне розташування книжок, надсилаючи запити машині. Оскільки машина стара, їй можна надіслати не більше ніж $5\,000$ запитів.

Напишіть програму, яка за інформацією про книжкову полицю визначає правильне розташування книжок, надсилаючи не більше ніж $5\,000$ запитів.

Деталі реалізації

Потрібно надіслати один файл.

Цей файл — library3.cpp. Він має реалізовувати наведену нижче функцію. Програма повинна підключати library3.h за допомогою директиви препроцесора #include.

• void solve(int N)

  Цю функцію викликають лише один раз для кожного тестового випадку.

  • Параметр N — кількість книжок $N$.

У library3.cpp можна викликати наведену нижче функцію.

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

  За допомогою цієї функції IOI-chan надсилає запит машині.

  • Параметр a — масив довжини $N$, що задає розташування $N$ книжок у запиті. Це означає, що у вказаному розташуванні книжка a[i] ($0 \le i \le N-1$) має стояти на місці $i$.
  • Повернене значення — кількість операцій, потрібних для повернення всіх книжок до правильного розташування, починаючи з указаного розташування.
  • Довжина параметра a має дорівнювати $N$. Якщо ця умова не виконується, програма отримає вердикт Неправильна відповідь [1].
  • Кожен елемент параметра a має бути від $0$ до $N-1$. Якщо ця умова не виконується, програма отримає вердикт Неправильна відповідь [2].
  • Кожен елемент параметра a має відрізнятися від усіх інших. Якщо ця умова не виконується, програма отримає вердикт Неправильна відповідь [3].
  • Не можна викликати функцію query строго більше ніж $5\,000$ разів. Якщо її викликати більше ніж $5\,000$ разів, програма отримає вердикт Неправильна відповідь [4].

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

  Викликаючи цю функцію, програма повідомляє правильне розташування книжок.

  • Параметр b — масив довжини $N$, що задає розташування $N$ книжок у відповіді. Це означає, що в повідомленому розташуванні книжка b[i] ($0 \le i \le N-1$) має стояти на місці $i$.
  • Довжина параметра b має дорівнювати $N$. Якщо ця умова не виконується, програма отримає вердикт Неправильна відповідь [5].
  • Кожен елемент параметра b має бути від $0$ до $N-1$. Якщо ця умова не виконується, програма отримає вердикт Неправильна відповідь [6].
  • Кожен елемент параметра b має відрізнятися від усіх інших. Якщо ця умова не виконується, програма отримає вердикт Неправильна відповідь [7].
  • Повідомлене розташування має бути правильним. Якщо ця умова не виконується, програма отримає вердикт Неправильна відповідь [8].
  • Функцію answer потрібно викликати рівно один раз. Якщо її викликати більше ніж 1 раз, програма отримає вердикт Неправильна відповідь [9]. Якщо на момент завершення функції solve функцію answer не було викликано, програма отримає вердикт Неправильна відповідь [10].

Важливе зауваження

• Програма може реалізовувати інші функції для внутрішнього використання або використовувати глобальні змінні.
• Програма не повинна використовувати стандартне введення та стандартне виведення. Програма не повинна взаємодіяти з іншими файлами в будь-який спосіб. Однак програма може виводити налагоджувальну інформацію в стандартний потік помилок.

Компіляція та тестування

З вебсторінки змагання можна завантажити архів, що містить приклад перевіряльної програми для тестування вашої програми. Архів також містить приклад вихідного коду вашої програми.

Приклад перевіряльної програми — файл grader.cpp. Щоб протестувати програму, помістіть grader.cpp, library3.cpp та library3.h в одну директорію та виконайте наведену нижче команду для компіляції. Натомість можна запустити compile.sh, що міститься в архіві.

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

Після успішної компіляції буде створено виконуваний файл grader.

Зверніть увагу, що справжня перевіряльна програма відрізняється від прикладу. Приклад перевіряльної програми запускається як один процес, що читає вхідні дані зі стандартного введення та записує результати в стандартне виведення.

Вхідні дані для прикладу перевіряльної програми

Приклад перевіряльної програми читає такі дані зі стандартного введення.

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

$B_i$ ($0 \le i \le N-1$) — номер книжки, що стоїть на місці $i$ у правильному розташуванні.

Вихідні дані прикладу перевіряльної програми

Приклад перевіряльної програми виводить таку інформацію в стандартне виведення та стандартний потік помилок (лапки наведено для ясності).

• Якщо програму визнано правильною, приклад перевіряльної програми повідомляє кількість викликів query у вигляді Accepted: 3000.
• Якщо програма отримує будь-який тип вердикту Неправильна відповідь, приклад перевіряльної програми виводить його тип у вигляді Wrong Answer [3].

Якщо програма задовольняє умови кількох типів вердикту Неправильна відповідь, приклад перевіряльної програми повідомляє лише один із них.

Обмеження

Усі вхідні дані задовольняють такі умови.

• $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$).
• Усі задані значення є цілими числами.

Підзадачі

1. (2 бали) $N \le 6$.
2. (19 балів) $N \le 100$.
3. (79 балів) Додаткових обмежень немає.

Приклад взаємодії

Нижче наведено приклад вхідних даних для прикладу перевіряльної програми та відповідних викликів функцій.

Вхідні дані 1

4
2 0 3 1

Приклад викликів функцій

Пояснення

Наприклад, виклик query([0, 1, 2, 3]) задає розташування, в якому книжки $0,1,2,3$ стоять на місцях $0,1,2,3$ відповідно. Операції повторюватимуться так:

1. Поміняти місцями книжку $0$ і книжку $1$. На місцях $0,1,2,3$ стоять книжки $1,0,2,3$ відповідно.
2. Поміняти місцями книжку $1$ і книжку $3$. На місцях $0,1,2,3$ стоять книжки $3,0,2,1$ відповідно.
3. Поміняти місцями книжку $3$ і книжку $2$. На місцях $0,1,2,3$ стоять книжки $2,0,3,1$ відповідно.

Оскільки для повернення всіх книжок до правильного розташування потрібно $3$ операції, повернене значення дорівнює $3$.

Ці вхідні дані прикладу задовольняють обмеження всіх підзадач.