题目描述

Yan 是个勇敢的男孩。一天他路过森林时，遇到了可怕的生物 Tung Tung Sahur。怪物决定和他玩一个游戏：

它会先选定一个隐藏排列 $P$，长度为 $N$。

之后 Yan 可以反复进行如下操作：

• 选择排列中的两个不同位置；
• 要求怪物交换这两个位置上的元素；
• 怪物执行交换后，会告诉 Yan：交换后的排列共有多少个置换环。

注意，这些交换是持久的，不会自动撤销。但如果 Yan 愿意，也可以再次交换同一对位置，从而把排列恢复回去。

在任意时刻，Yan 都可以宣布排列已经有序。如果此时排列确实满足

那么 Yan 就获胜。

你的任务是帮助 Yan，只通过这些交换后返回的“环数”信息，把隐藏排列排成升序，并尽量减少交换次数。

实现细节

你需要实现以下函数：

void sortPermutation(int N);

该函数会被每组测试调用一次，其中 $N$ 是排列长度。

在你的代码中，你可以调用评测器提供的函数：

int performSwap(int x, int y);

它表示交换 $P_x$ 和 $P_y$，其中 $x,y$ 为 0-based 下标，并返回交换后排列中的环数。

注意：

• 必须保证 $x \ne y$；
• 若调用时 $x = y$，将直接得到 Wrong Answer；
• 当 sortPermutation 返回后，评测器会立刻认为你已经宣布“Sorted”，因此此时隐藏排列必须已经被正确排好序。

额外要求

• 你的代码会与 grader 一起编译；
• 你不应实现 main 函数；
• 也不应自行读写标准输入输出；
• 需要包含头文件 cycles.h；
• 评测器不是自适应的，隐藏排列在整个测试过程中固定不变。

本地测试

本地提供了评测器和头文件。

本地输入格式为：

• 第一行：整数 $N$
• 第二行：$N$ 个互不相同的整数，取值范围为 $0$ 到 $N-1$，表示初始隐藏排列

之后评测器会调用你的 sortPermutation，并检查排列是否被正确排成升序。

数据范围

• $N = 1000$

子任务

评分规则

设 $Q$ 为你在所有测试中调用 performSwap 的最大次数。

样例

样例输入（本地评测器格式）

3
2 0 1

样例交互

sortPermutation(3)
performSwap(0, 1): return 2
performSwap(0, 1): return 1
performSwap(0, 1): return 2
performSwap(1, 2): return 3
sortPermutation(3): returns