题目描述

Peshо 的房间里有一个书架，上面放着 N 本笔记本，里面记着他脑海中所有天才想法的描述。笔记本编号为 1 到 N。Peshо 有自己最喜欢的一种摆放顺序，这个顺序不一定按编号递增，他也非常不喜欢别人把它们重新摆乱。

Peshо 买了一个特殊机器人，它能够记住笔记本的摆放顺序，并计算该顺序中的逆序对数。机器人认为：如果编号较小的笔记本放在编号较大的笔记本右边，那么这两本笔记本就构成一对逆序。例如，在排列 (2,1,5,3,4) 中，有三对逆序：(2,1)、(5,3) 和 (5,4)，因此该排列的逆序对数为 3。

不幸的是，房间装修后，书架上的笔记本被打乱了，而 Peshо 忘记了自己最喜欢的摆法。机器人还记得，但它只能报告自己当前记住的排列的逆序对数。Peshо 可以要求机器人把它当前记住的排列中两本笔记本的位置交换。交换后，机器人会记住这个新排列（忘掉旧的），并报告新排列的逆序对数。

Peshо 可以不断向机器人提出这样的请求，直到他认为自己已经获得了足够的信息，可以恢复出原来的最喜欢摆法。

你将扮演 Peshо，而评测程序扮演机器人。

任务

编写函数 bookshelf()，它将与评测程序一起编译，并不断向评测程序提问，直到恢复出最初的笔记本排列。

实现细节

你需要实现如下函数：

void bookshelf(int N, long long Inv);

该函数由评测程序调用一次，其中：

• N 表示笔记本数量；
• Inv 表示初始排列中的逆序对数。

评测程序还会提供以下函数供你调用：

long long bookswap(int i, int j);
void answer(int p[]);

其中：

• 调用 bookswap(i, j) 表示请求评测程序将当前排列中位置 i 和位置 j 的笔记本交换，并返回交换后排列中的逆序对数；
• 当你认为已经恢复出初始排列时，需要调用 answer(p)。其中 p[i] 表示当前你给出的答案中，位置 i 上的笔记本编号。

你需要向系统提交文件 bookshelf.cpp，其中包含函数 bookshelf()。文件中可以包含其他辅助代码，但不能包含 main()。

你的文件开头必须写有：

#include "bookshelf.h"

限制

• 2 ≤ N ≤ 100000
• 对机器人发出的交换请求总数满足 0 ≤ 请求数 ≤ 200000
• 在 10% 的测试中，2 ≤ N ≤ 400
• 在另外 20% 的测试中，400 < N ≤ 5000
• 在另外 30% 的测试中，5000 < N ≤ 50000

评分方式

每个测试点单独计分。

示例交互

设你的程序需要猜出的初始排列为：

4 3 1 5 2

该排列中的逆序对数为 6，分别是：

• (4,3)
• (4,1)
• (4,2)
• (3,1)
• (3,2)
• (5,2)

于是评测程序会这样调用你的函数：

bookshelf(5, 6);

原题给出的一个可能对话如下：

说明：原 PDF 示例中最后一行写作 bookswap(5,6)；由于此前设定 N = 5，这一行看起来像是原题排版或原文笔误。这里按原题原样保留，未擅自修改。

本地测试

原题提供了 Lgrader.cpp 和 bookshelf.h 用于本地测试。将它们与你的 bookshelf.cpp 一起编译即可。

本地测试程序从标准输入读取：

• 第一行：两个正整数，分别为笔记本数和初始排列的逆序对数；
• 第二行：初始排列本身。

程序输出你的函数“猜出”的初始排列。