题意

原题链接

中文简化版：

给定一个排列 ，你可以进行任意次以下操作：

• 选择相邻的四个位置 ，交换 和 ，交换 和 ；换句话说，若序列原本是 ，操作后变为 。

最小化排列的字典序。

做法

首先可以糊一个假做法。

注意到每次操作不会将奇数位置与偶数位置交换，而是只会交换奇数列和偶数列相邻位置的数。因此考虑对奇数列和偶数列分别排序。

然后 Wrong Answer on pretest 2。

（好像 AI 会卡在这里）

反例是容易构造的，但是多次模拟可以发现，最多只有最后 位无法排序。

注意到，由于序列是一个排列，每个数互不相同，因此交换相邻两个数必定会使逆序对 。

因此，若奇数列和偶数列的逆序对奇偶性相同，则可以对奇数列和偶数列分别排序，否则只需再交换倒数第 位和倒数第 位即可。

听说暴力模拟也能过。