Sau vài trăm năm, thành phố JOI đã trở thành phế tích. Nhà thám hiểm IOI-chan hiện đang khám phá khu vực từng xây thư viện. Qua quá trình khám phá, cô biết được những điều sau:

• Trong thư viện của thành phố JOI từng có một giá sách nằm ngang. Giá có $N$ vị trí xếp thành một hàng để đặt sách, được đánh số từ $0$ đến $N-1$ từ trái sang phải. Mỗi vị trí chỉ đặt được đúng một cuốn sách.
• Có $N$ cuốn sách trên giá. Các cuốn sách được đánh số từ $0$ đến $N-1$.
• Một cách sắp xếp sách là cách đặt toàn bộ $N$ cuốn sách vào $N$ vị trí.
• Có một cách sắp xếp đúng của các cuốn sách, trong đó cuốn sách $B_i$ ($0\le i\le N-1$) được đặt tại vị trí $i$. Các giá trị $B_i$ đôi một khác nhau.

Cách sắp xếp sách thường bị thay đổi. Ta biết rằng tại thư viện này, người ta đưa sách về cách sắp xếp đúng bằng cách lặp lại thao tác sau.

Thao tác: Gọi cuốn sách $x$ là cuốn sách nằm ngoài cùng bên trái trong số các cuốn có vị trí khác với vị trí của chúng trong cách sắp xếp đúng. Gọi cuốn sách $y$ là cuốn hiện đang nằm tại vị trí mà cuốn sách $x$ phải nằm trong cách sắp xếp đúng. Hoán đổi vị trí của cuốn sách $x$ và cuốn sách $y$.

Mặc dù IOI-chan đã tìm thấy những cuốn sách cũ của thư viện, cô không biết cách sắp xếp đúng. Nhưng cô tìm thấy một cỗ máy cũ từng quản lý các thao tác trên giá sách. Nếu chỉ định một cách sắp xếp $N$ cuốn sách và gửi truy vấn cho máy, máy sẽ trả lời số thao tác cần để đưa tất cả sách về cách sắp xếp đúng. IOI-chan muốn tìm ra cách sắp xếp đúng bằng cách gửi truy vấn cho máy. Vì máy đã cũ, cô chỉ có thể gửi tối đa $5\,000$ truy vấn.

Hãy viết chương trình nhận thông tin về giá sách và xác định cách sắp xếp đúng bằng cách gửi tối đa $5\,000$ truy vấn.

Chi tiết cài đặt

Bạn cần nộp một tệp.

Tệp này có tên library3.cpp. Nó phải cài đặt hàm sau. Chương trình phải bao gồm library3.h bằng chỉ thị tiền xử lý #include.

• void solve(int N)

  Hàm này được gọi đúng một lần cho mỗi bộ kiểm thử.

  • Tham số N là số cuốn sách $N$.

Trong library3.cpp, bạn có thể gọi các hàm sau.

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

  IOI-chan dùng hàm này để gửi một truy vấn cho máy.

  • Tham số a là một mảng có độ dài $N$, biểu diễn cách sắp xếp $N$ cuốn sách được chỉ định trong truy vấn. Nghĩa là, trong cách sắp xếp đó, cuốn sách a[i] ($0\le i\le N-1$) phải nằm tại vị trí $i$.
  • Giá trị trả về là số thao tác cần để đưa tất cả sách về cách sắp xếp đúng, bắt đầu từ cách sắp xếp đã chỉ định.
  • Độ dài của tham số a phải bằng $N$. Nếu không thỏa mãn điều kiện này, chương trình sẽ bị chấm là đáp án sai Wrong Answer [1].
  • Mỗi phần tử của tham số a phải nằm trong khoảng từ $0$ đến $N-1$. Nếu không thỏa mãn điều kiện này, chương trình sẽ bị chấm là đáp án sai Wrong Answer [2].
  • Các phần tử của tham số a phải đôi một khác nhau. Nếu không thỏa mãn điều kiện này, chương trình sẽ bị chấm là đáp án sai Wrong Answer [3].
  • Bạn không được gọi hàm query quá $5\,000$ lần. Nếu gọi quá $5\,000$ lần, chương trình sẽ bị chấm là đáp án sai Wrong Answer [4].

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

  Chương trình trả lời cách sắp xếp đúng của các cuốn sách bằng cách gọi hàm này.

  • Tham số b là một mảng có độ dài $N$, biểu diễn cách sắp xếp $N$ cuốn sách được chỉ định trong câu trả lời. Nghĩa là, trong cách sắp xếp được trả lời, cuốn sách b[i] ($0\le i\le N-1$) phải nằm tại vị trí $i$.
  • Độ dài của tham số b phải bằng $N$. Nếu không thỏa mãn điều kiện này, chương trình sẽ bị chấm là đáp án sai Wrong Answer [5].
  • Mỗi phần tử của tham số b phải nằm trong khoảng từ $0$ đến $N-1$. Nếu không thỏa mãn điều kiện này, chương trình sẽ bị chấm là đáp án sai Wrong Answer [6].
  • Các phần tử của tham số b phải đôi một khác nhau. Nếu không thỏa mãn điều kiện này, chương trình sẽ bị chấm là đáp án sai Wrong Answer [7].
  • Cách sắp xếp được trả lời phải là cách sắp xếp đúng. Nếu không thỏa mãn điều kiện này, chương trình sẽ bị chấm là đáp án sai Wrong Answer [8].
  • Hàm answer phải được gọi đúng một lần. Nếu gọi quá một lần, chương trình sẽ bị chấm là đáp án sai Wrong Answer [9]. Khi hàm solve kết thúc, nếu chưa gọi hàm answer, chương trình sẽ bị chấm là đáp án sai Wrong Answer [10].

Lưu ý quan trọng

• Chương trình có thể cài đặt các hàm khác để dùng nội bộ hoặc sử dụng biến toàn cục.
• Chương trình không được sử dụng đầu vào chuẩn và đầu ra chuẩn. Chương trình không được giao tiếp với các tệp khác bằng bất kỳ phương thức nào. Tuy nhiên, chương trình được phép in thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Biên dịch và chạy thử

Bạn có thể tải từ trang web cuộc thi một tệp nén chứa trình chấm mẫu để kiểm tra chương trình. Tệp nén cũng chứa một tệp mã nguồn mẫu của chương trình.

Trình chấm mẫu là tệp grader.cpp. Để kiểm tra chương trình, hãy đặt grader.cpp, library3.cpp và library3.h trong cùng một thư mục, rồi chạy lệnh sau để biên dịch các chương trình. Thay vào đó, bạn có thể chạy compile.sh có trong tệp nén.

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

Khi biên dịch thành công, tệp thực thi grader được tạo ra.

Lưu ý rằng trình chấm thực tế khác với trình chấm mẫu. Trình chấm mẫu chạy dưới dạng một tiến trình duy nhất, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào cho trình chấm mẫu

Trình chấm mẫu đọc dữ liệu sau từ đầu vào chuẩn.

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

$B_i$ ($0\le i\le N-1$) là số hiệu của cuốn sách nằm tại vị trí $i$ trong cách sắp xếp đúng.

Dữ liệu ra của trình chấm mẫu

Trình chấm mẫu in thông tin sau ra đầu ra chuẩn và đầu ra lỗi chuẩn (dấu ngoặc kép được dùng để làm rõ).

• Nếu chương trình được chấm là đúng, trình chấm báo số lần gọi query theo dạng Accepted: 3000.
• Nếu chương trình bị chấm là đáp án sai thuộc bất kỳ loại nào, trình chấm mẫu in loại đó theo dạng Wrong Answer [3].

Nếu chương trình thỏa mãn điều kiện của nhiều loại đáp án sai, trình chấm mẫu chỉ báo một loại.

Giới hạn

Tất cả dữ liệu vào thỏa mãn các điều kiện sau.

• $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$).
• Các giá trị đã cho đều là số nguyên.

Nhiệm vụ con

1. (2 điểm) $N\le 6$.
2. (19 điểm) $N\le 100$.
3. (79 điểm) Không có giới hạn bổ sung.

Ví dụ

Dưới đây là dữ liệu vào mẫu cho trình chấm mẫu và các lời gọi hàm tương ứng.

Dữ liệu vào 1

4
2 0 3 1

Ghi chú

Các lời gọi hàm mẫu:

Ví dụ, lời gọi query([0, 1, 2, 3]) chỉ định cách sắp xếp trong đó các cuốn sách $0,1,2,3$ lần lượt nằm tại các vị trí $0,1,2,3$. Thao tác sẽ được lặp lại như sau.

1. Hoán đổi vị trí của cuốn sách $0$ và cuốn sách $1$. Các cuốn sách $1,0,2,3$ lần lượt nằm tại các vị trí $0,1,2,3$.
2. Hoán đổi vị trí của cuốn sách $1$ và cuốn sách $3$. Các cuốn sách $3,0,2,1$ lần lượt nằm tại các vị trí $0,1,2,3$.
3. Hoán đổi vị trí của cuốn sách $3$ và cuốn sách $2$. Các cuốn sách $2,0,3,1$ lần lượt nằm tại các vị trí $0,1,2,3$.

Vì số thao tác cần để đưa tất cả sách về cách sắp xếp đúng là $3$, giá trị trả về là $3$.

Dữ liệu vào mẫu này thỏa mãn giới hạn của tất cả nhiệm vụ con.