经过数百年的岁月，JOI 市变成了一座废墟。探险家 IOI-chan 正在探索这座图书馆的遗址。根据探索结果，已知以下信息：
- JOI 市的图书馆里有一个水平书架。书架上有 $N$ 个位置，从左到右编号为 $0$ 到 $N - 1$。每个位置恰好可以放一本书。
- 书架上有 $N$ 本书，编号为 $0$ 到 $N - 1$。
- 书的排列方式是指将所有 $N$ 本书放置在 $N$ 个位置上的方式。
- 存在一种正确的排列方式，其中书 $B_i$ ($0 \le i \le N - 1$) 被放置在位置 $i$。保证 $B_i$ 互不相同。
书的排列经常会发生变化。我们知道，在这个图书馆中，书是通过重复执行以下操作来恢复到正确排列的。
操作：令书 $x$ 为当前排列中，位置与正确排列不符的书中最靠左的一本。令书 $y$ 为当前排列中，位于书 $x$ 在正确排列中应处位置上的那本书。交换书 $x$ 和书 $y$ 的位置。
虽然 IOI-chan 找到了图书馆的旧书，但她不知道正确的排列方式。不过，她发现了一台可以管理书架操作的旧机器。如果我们指定 $N$ 本书的排列方式并向机器发送查询，它会返回将所有书恢复到正确排列所需的操作次数。IOI-chan 希望通过向机器发送查询来获知书的正确排列方式。由于机器很旧，她最多只能向机器发送 $5\,000$ 次查询。
请编写一个程序，在给定书架信息的情况下，通过发送最多 $5\,000$ 次查询来确定书的正确排列方式。
实现细节
你需要提交一个文件。
文件名为 library3.cpp。它应该实现以下函数。程序应使用预处理指令 #include 包含 library3.h。
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$。如果不满足此条件，你的程序将被判为 Wrong Answer [1]。
- 参数 $a$ 的每个元素必须在 $0$ 到 $N - 1$ 之间。如果不满足此条件，你的程序将被判为 Wrong Answer [2]。
- 参数 $a$ 的每个元素必须互不相同。如果不满足此条件，你的程序将被判为 Wrong Answer [3]。
- 你调用
query函数的次数不得严格超过 $5\,000$ 次。如果调用次数超过 $5\,000$ 次，你的程序将被判为 Wrong Answer [4]。
void answer(std::vector<int> b)你的程序通过调用此函数来回答书的正确排列方式。- 参数 $b$ 是一个长度为 $N$ 的数组，表示答案中指定的 $N$ 本书的排列方式。这意味着在回答的排列中，书 $b[i]$ ($0 \le i \le N - 1$) 必须放置在位置 $i$。
- 参数 $b$ 的长度必须为 $N$。如果不满足此条件，你的程序将被判为 Wrong Answer [5]。
- 参数 $b$ 的每个元素必须在 $0$ 到 $N - 1$ 之间。如果不满足此条件，你的程序将被判为 Wrong Answer [6]。
- 参数 $b$ 的每个元素必须互不相同。如果不满足此条件，你的程序将被判为 Wrong Answer [7]。
- 回答的排列必须是正确的排列。如果不满足此条件，你的程序将被判为 Wrong Answer [8]。
answer函数必须且仅能被调用一次。如果调用次数超过 $1$ 次，你的程序将被判为 Wrong Answer [9]。当solve函数终止时，如果未调用answer函数，你的程序将被判为 Wrong Answer [10]。
说明
- 你的程序可以实现其他内部函数或使用全局变量。
- 你的程序不得使用标准输入和标准输出。你的程序不得通过任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。
数据范围
所有输入数据满足以下条件： $2 \le N \le 500$。 $0 \le B_i \le N - 1$ ($0 \le i \le N - 1$)。 $B_i \neq B_j$ ($0 \le i < j \le N - 1$)。 给定值均为整数。
子任务
- (2 分) $N \le 6$。
- (19 分) $N \le 100$。
- (79 分) 无附加限制。
样例
样例 1
4 2 0 3 1
| 调用 | 返回值 |
|---|---|
solve(4) |
|
query([0, 1, 2, 3]) |
3 |
query([1, 3, 0, 2]) |
2 |
query([3, 0, 1, 2]) |
2 |
query([2, 0, 3, 1]) |
0 |
answer([2, 0, 3, 1]) |
例如，调用 query([0, 1, 2, 3]) 指定了书 0, 1, 2, 3 分别放置在位置 0, 1, 2, 3 的排列。操作将按如下方式重复：
- 交换书 0 和书 1 的位置。书 1, 0, 2, 3 分别放置在位置 0, 1, 2, 3。
- 交换书 1 和书 3 的位置。书 3, 0, 2, 1 分别放置在位置 0, 1, 2, 3。
- 交换书 3 和书 2 的位置。书 2, 0, 3, 1 分别放置在位置 0, 1, 2, 3。
由于将所有书恢复到正确排列所需的操作次数为 3，因此返回值为 3。 该样例输入满足所有子任务的限制。