题目重述

你有一个长度为 $n$ 的排列 $a$，允许进行任意次操作：选择 $1 \le i \le n-3$，同时交换 $a_i$ 与 $a_{i+2}$，以及 $a_{i+1}$ 与 $a_{i+3}$。

目标：通过这种操作能得到的最小字典序排列。

---

操作的本质

一次操作将四元组：

$$[a_i, a_{i+1}, a_{i+2}, a_{i+3}] \to [a_{i+2}, a_{i+3}, a_i, a_{i+1}] $$

观察这个变换，可以发现：

1. 位置奇偶性不变：
   原来在奇数位置（$i$ 是奇数）的元素，操作后仍然在奇数位置。
   原来在偶数位置（$i+1$ 是偶数）的元素，操作后仍然在偶数位置。
   因为 $i$ 和 $i+2$ 同奇偶，$i+1$ 和 $i+3$ 同奇偶。

2. 奇数位置上的元素只能在奇数位置之间交换，偶数位置上的元素只能在偶数位置之间交换。

3. 实际上，这种操作允许我们在奇数列内做相邻交换（通过组合操作），在偶数列内也做相邻交换。

---

关键结论

设：

• 原排列的奇数位置上的元素序列：$a_1, a_3, a_5, \dots$
• 原排列的偶数位置上的元素序列：$a_2, a_4, a_6, \dots$

经过任意次操作，这两个子序列内部的相对顺序可以任意改变（因为可以通过类似冒泡排序的交换实现），但元素不能从一个子序列跳到另一个子序列。

因此，我们可以独立地将奇数位置子序列和偶数位置子序列分别排序为升序，从而得到字典序尽可能小的排列。

---

奇偶性限制带来的额外约束

两个子序列各自排序后，直接按位置放回原数组：

$$a_1 \le a_3 \le a_5 \le \dots, \quad a_2 \le a_4 \le a_6 \le \dots $$

此时是否一定能通过操作达到这个状态？不一定。
因为操作在交换四元组时，会同时改变两个子序列的逆序对奇偶性。

逆序对奇偶性的变化

一次操作相当于：

• 在奇数列中，交换了 $a_i$ 与 $a_{i+2}$（如果 $i$ 是奇数）或 $a_{i+1}$ 与 $a_{i+3}$（如果 $i$ 是偶数）——注意，这取决于 $i$ 的奇偶性。实际上：
  • 若 $i$ 是奇数：交换了奇数位置的 $i$ 和 $i+2$。
  • 若 $i$ 是偶数：交换了偶数位置的 $i$ 和 $i+2$。

但仔细看操作定义：同时交换 $a_i$ 与 $a_{i+2}$，$a_{i+1}$ 与 $a_{i+3}$。

• 如果 $i$ 是奇数：则 $i$ 和 $i+2$ 是奇数位置，$i+1$ 和 $i+3$ 是偶数位置。
• 如果 $i$ 是偶数：则 $i$ 和 $i+2$ 是偶数位置，$i+1$ 和 $i+3$ 是奇数位置。

所以一次操作同时交换了：

• 奇数子序列中的两个元素（距离为 2）
• 偶数子序列中的两个元素（距离为 2）

在奇数子序列中，两个元素的距离为 $2$ 意味着它们在子序列中位置相差 $1$（因为子序列的相邻元素在原数组中距离为 2）。因此，一次操作相当于同时在两个子序列中交换相邻元素。

---

交换相邻元素对逆序对的影响

在一个序列中，交换相邻元素会改变该序列的逆序对数的奇偶性（即逆序对数 $\pm 1$，改变 $1$ 的奇偶性）。

因此，一次操作同时交换：

• 奇数子序列的某两个相邻元素（改变奇子序列逆序对奇偶性）
• 偶数子序列的某两个相邻元素（改变偶子序列逆序对奇偶性）

所以，两个子序列的逆序对数的奇偶性会同时改变（都翻转）。

结论：在任意可达状态中，两个子序列的逆序对数的奇偶性之差保持不变（因为两者同时改变，差不变）。

---

初始状态与目标状态

初始状态：计算奇子序列的逆序对数 $inv_{odd}$，偶子序列的逆序对数 $inv_{even}$。
它们的差 $d = (inv_{odd} - inv_{even}) \bmod 2$ 是一个不变量。

目标状态（各自排序后）：奇子序列、偶子序列都是升序，所以 $inv_{odd} = 0$，$inv_{even} = 0$。
此时 $d' = 0$。

因此，只有 $d = 0$ 时才能达到这个“完美排序”状态。

如果 $d = 1$，则无法同时让两个子序列都完全排序。但我们可以让其中一个子序列完全排序，另一个子序列只差一次相邻交换（即差一个逆序对）。

---

最小字典序排列的构造

为了得到字典序最小的排列，我们希望前面的位置尽可能小。
由于位置 1 是奇数位置，我们希望 $a_1$ 最小 → 把奇子序列的最小元素放在位置 1；
然后位置 2 是偶数位置，我们希望 $a_2$ 最小 → 把偶子序列的最小元素放在位置 2；
依次类推。

所以，将奇子序列升序排列，偶子序列升序排列，然后按位置交错放置，得到：

$$[odd_1, even_1, odd_2, even_2, \dots]$$

这是不考虑奇偶性约束时的理想排列。

如果 $d = 0$，这个排列可以直接达到。

如果 $d = 1$，这个排列无法达到。为了修正，我们可以在最后交换位置 $n$ 和 $n-2$（即最后一个奇数位置和它前面的奇数位置），因为：

• 位置 $n$ 和 $n-2$ 同奇偶（取决于 $n$ 的奇偶性），交换它们只改变该子序列的一个逆序对，从而修正奇偶性。
• 这个交换对字典序影响最小，因为越靠后的位置权重越小。

---

代码对应解析

int f(vector<int> x) {
    // 计算逆序对数（树状数组实现）
    rep(i, 0, n) fen[i] = 0;
    int ans = 0;
    per(i, sz(x)-1, 0) {
        ans += que(x[i]);
        upd(x[i]);
    }
    return ans;
}

f(x) 返回序列 x 的逆序对数。

---

vector<int> a1, a2;
rep(i, 1, n) {
    int x; cin >> x;
    if (i % 2 == 1) a1.pb(x);
    else a2.pb(x);
}

将原排列按位置奇偶性拆分为两个子序列。

---

bool v = (f(a1) % 2 != f(a2) % 2);

计算 $d$（逆序对数奇偶性是否不同），v = true 表示无法同时完全排序。

---

sort(all(a1)); sort(all(a2));
int x1 = 0, x2 = 0;
rep(i, 1, n) {
    if (i % 2 == 1) a[i] = a1[x1++];
    else a[i] = a2[x2++];
}

构造理想排列（各自排序后交错放置）。

---

if (v) {
    swap(a[n], a[n-2]);
}

如果奇偶性不匹配，交换最后两个奇数位置上的元素（假设 $n$ 是偶数时 $n-2$ 也是偶数？这里需要验证）。

实际上代码中 swap(a[n], a[n-2]) 交换的是第 $n$ 和 $n-2$ 个元素。

• 如果 $n$ 是偶数，$n$ 和 $n-2$ 都是偶数位置。
• 如果 $n$ 是奇数，$n$ 和 $n-2$ 都是奇数位置。

所以这是在同一子序列内部交换相邻元素（在子序列中位置差 1），从而改变该子序列逆序对奇偶性。
由于 $d = 1$，我们只需改变其中一个子序列的奇偶性，就能让两者都是偶数（即 0 mod 2）。
选择交换最后一对相邻元素，对字典序影响最小。

---

总结

1. 操作保持元素的位置奇偶性不变。
2. 奇子序列和偶子序列内部可以任意重排。
3. 两个子序列的逆序对数奇偶性之差是操作不变量。
4. 最小字典序策略：各自排序后交错放置。
5. 若奇偶性不匹配，则交换最后两个同奇偶位置上的元素修正。

时间复杂度：$O(n \log n)$（排序 + 逆序对计算）。