Setelah beberapa ratus tahun berlalu, kota JOI menjadi reruntuhan. IOI-chan, seorang penjelajah, kini sedang menjelajahi daerah tempat perpustakaan dahulu dibangun. Berdasarkan hasil penjelajahan, diketahui hal-hal berikut:

• Di perpustakaan kota JOI terdapat sebuah rak buku horizontal. Rak itu memiliki $N$ tempat untuk meletakkan buku dalam satu baris, bernomor $0$ sampai $N-1$ dari kiri ke kanan. Tepat satu buku dapat diletakkan di setiap tempat.
• Terdapat $N$ buku di rak tersebut. Buku-buku itu bernomor $0$ sampai $N-1$.
• Susunan buku adalah cara menempatkan semua $N$ buku pada $N$ tempat.
• Terdapat susunan yang benar, dan dalam susunan itu buku $B_i$ ($0 \le i \le N-1$) berada di tempat $i$. Semua $B_i$ berbeda.

Susunan buku sering berubah. Diketahui bahwa di perpustakaan ini, buku-buku dikembalikan ke susunan yang benar dengan mengulangi operasi berikut.

Operasi: Misalkan buku $x$ adalah buku paling kiri di antara buku-buku yang tempatnya berbeda dari tempatnya dalam susunan yang benar. Misalkan pula buku $y$ adalah buku yang saat ini berada di tempat yang seharusnya ditempati buku $x$ dalam susunan yang benar. Tukar tempat buku $x$ dan buku $y$.

Walaupun IOI-chan menemukan buku-buku lama perpustakaan itu, ia tidak dapat mengetahui susunan yang benar. Namun, ia menemukan mesin tua yang dahulu mengelola operasi pada rak buku perpustakaan. Jika kita menentukan suatu susunan $N$ buku dan mengirim kueri ke mesin, mesin menjawab jumlah operasi yang diperlukan untuk mengembalikan semua buku ke susunan yang benar. IOI-chan ingin mengetahui susunan buku yang benar dengan mengirim kueri ke mesin. Karena mesin sudah tua, ia hanya dapat mengirim paling banyak $5\,000$ kueri.

Tulislah program yang, diberikan informasi tentang rak buku, menentukan susunan buku yang benar dengan mengirim paling banyak $5\,000$ kueri.

Detail Implementasi

Anda harus mengumpulkan satu berkas.

Berkas tersebut adalah library3.cpp. Berkas ini harus mengimplementasikan fungsi berikut. Program harus menyertakan library3.h menggunakan direktif praprosesor #include.

void solve(int N)

Fungsi ini dipanggil tepat satu kali untuk setiap kasus uji.

• Parameter N adalah jumlah buku $N$.

Dalam library3.cpp, Anda dapat memanggil fungsi-fungsi berikut.

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

Dengan fungsi ini, IOI-chan mengirim kueri ke mesin.

• Parameter a adalah larik sepanjang $N$ yang menunjukkan susunan $N$ buku yang ditentukan dalam kueri. Artinya, dalam susunan tersebut, buku a[i] ($0 \le i \le N-1$) harus diletakkan di tempat $i$.
• Nilai kembaliannya adalah jumlah operasi yang diperlukan untuk mengembalikan semua buku ke susunan yang benar, dimulai dari susunan yang ditentukan.
• Panjang parameter a harus $N$. Jika syarat ini tidak dipenuhi, program Anda mendapat putusan Wrong Answer [1].
• Setiap elemen parameter a harus antara $0$ dan $N-1$. Jika syarat ini tidak dipenuhi, program Anda mendapat putusan Wrong Answer [2].
• Semua elemen parameter a harus berbeda satu sama lain. Jika syarat ini tidak dipenuhi, program Anda mendapat putusan Wrong Answer [3].
• Anda tidak boleh memanggil fungsi query lebih dari $5\,000$ kali. Jika dipanggil lebih dari $5\,000$ kali, program Anda mendapat putusan Wrong Answer [4].

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

Program Anda memberikan jawaban berupa susunan buku yang benar dengan memanggil fungsi ini.

• Parameter b adalah larik sepanjang $N$ yang menunjukkan susunan $N$ buku yang ditentukan dalam jawaban. Artinya, dalam susunan yang dijawab, buku b[i] ($0 \le i \le N-1$) harus diletakkan di tempat $i$.
• Panjang parameter b harus $N$. Jika syarat ini tidak dipenuhi, program Anda mendapat putusan Wrong Answer [5].
• Setiap elemen parameter b harus antara $0$ dan $N-1$. Jika syarat ini tidak dipenuhi, program Anda mendapat putusan Wrong Answer [6].
• Semua elemen parameter b harus berbeda satu sama lain. Jika syarat ini tidak dipenuhi, program Anda mendapat putusan Wrong Answer [7].
• Susunan yang dijawab harus merupakan susunan yang benar. Jika syarat ini tidak dipenuhi, program Anda mendapat putusan Wrong Answer [8].
• Fungsi answer harus dipanggil tepat satu kali. Jika dipanggil lebih dari 1 kali, program Anda mendapat putusan Wrong Answer [9]. Saat fungsi solve berakhir, jika fungsi answer belum dipanggil, program Anda mendapat putusan Wrong Answer [10].

Catatan Penting

• Program Anda dapat mengimplementasikan fungsi lain untuk penggunaan internal atau menggunakan variabel global.
• Program Anda tidak boleh menggunakan masukan standar dan keluaran standar. Program Anda tidak boleh berkomunikasi dengan berkas lain dengan cara apa pun. Namun, program Anda boleh menuliskan informasi debug ke keluaran galat standar.

Kompilasi dan Uji Coba

Anda dapat mengunduh berkas arsip dari laman lomba yang berisi grader contoh untuk menguji program Anda. Arsip ini juga berisi berkas kode sumber contoh untuk program Anda.

Grader contoh terdapat dalam berkas grader.cpp. Untuk menguji program, letakkan grader.cpp, library3.cpp, dan library3.h dalam direktori yang sama, lalu jalankan perintah berikut untuk mengompilasi program. Sebagai alternatif, Anda dapat menjalankan compile.sh yang terdapat dalam arsip.

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

Jika kompilasi berhasil, berkas eksekutabel grader akan dihasilkan.

Perhatikan bahwa grader sebenarnya berbeda dari grader contoh. Grader contoh dijalankan sebagai satu proses yang membaca data dari masukan standar dan menuliskan hasil ke keluaran standar.

Masukan untuk Grader Contoh

Grader contoh membaca data berikut dari masukan standar.

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

$B_i$ ($0 \le i \le N-1$) adalah nomor buku yang diletakkan di tempat $i$ dalam susunan yang benar.

Keluaran Grader Contoh

Grader contoh menuliskan informasi berikut ke keluaran standar dan keluaran galat standar (tanda kutip hanya untuk memperjelas).

• Jika program Anda dinilai benar, grader melaporkan jumlah pemanggilan query dalam format Accepted: 3000.
• Jika program Anda mendapat putusan Wrong Answer jenis apa pun, grader contoh menuliskan jenisnya, misalnya Wrong Answer [3].

Jika program Anda memenuhi syarat beberapa jenis Wrong Answer, grader contoh hanya melaporkan salah satunya.

Batasan

Semua data masukan memenuhi syarat berikut.

• $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$).
• Semua nilai yang diberikan adalah bilangan bulat.

Subtugas

1. (2 poin) $N \le 6$.
2. (19 poin) $N \le 100$.
3. (79 poin) Tidak ada batasan tambahan.

Contoh Interaksi

Berikut adalah masukan contoh untuk grader contoh beserta pemanggilan fungsi yang bersesuaian.

Masukan 1

4
2 0 3 1

Contoh Pemanggilan Fungsi

Penjelasan

Sebagai contoh, pemanggilan query([0, 1, 2, 3]) menentukan susunan dengan buku $0,1,2,3$ masing-masing berada di tempat $0,1,2,3$. Operasi diulangi sebagai berikut.

1. Tukar tempat buku $0$ dan buku $1$. Buku $1,0,2,3$ masing-masing berada di tempat $0,1,2,3$.
2. Tukar tempat buku $1$ dan buku $3$. Buku $3,0,2,1$ masing-masing berada di tempat $0,1,2,3$.
3. Tukar tempat buku $3$ dan buku $2$. Buku $2,0,3,1$ masing-masing berada di tempat $0,1,2,3$.

Karena jumlah operasi yang diperlukan untuk mengembalikan semua buku ke susunan yang benar adalah $3$, nilai kembaliannya adalah $3$.

Contoh ini memenuhi batasan semua subtugas.