题目理解

我们有一个长度为 $n$ 的数组 $a$，可以进行任意次操作：
选择 $i$，交换 $a_i$ 与 $a_{n-i+1}$（即关于中心对称的位置交换）。

目标：最小化扰动

也就是相邻相等元素的对数。

核心观察

• 操作允许我们将对称位置的元素任意排列，因为交换两次等于没动，且可以对多对不同位置独立操作（但要注意，$i$ 和 $n-i+1$ 独立于其他 $j$ 位置）。
• 事实上，考虑第 $i$ 对位置 $(i, n-i+1)$（当 $i < n-i+1$ 时），它们影响的是四个相邻关系：
  • $a_{i-1}$ 与 $a_i$
  • $a_i$ 与 $a_{i+1}$
  • $a_{n-i}$ 与 $a_{n-i+1}$
  • $a_{n-i+1}$ 与 $a_{n-i+2}$

由于 $a_i$ 和 $a_{n-i+1}$ 的内部交换只影响这些局部位置，我们可以独立地处理每一对对称位置，尝试减少扰动。

局部最优决策

对每一对 $(a_i, a_{n-i+1})$，在它们左边的元素是 $a_{i-1}$，右边的元素是 $a_{i+1}$（当 $i+1 \le n-i$ 时，保证不重叠？
注意：如果数组长度为奇数，中间元素 $i = n-i+1$ 时不能交换，但交换也不影响，因为是自己换自己。
所以只考虑 $i < n-i+1$。

简化问题

我们只关心这四个元素： 左邻居 $\text{left1} = a_{i-1}$，当前对中的一个 $\text{x} = a_i$，另一个 $\text{y} = a_{n-i+1}$，右邻居 $\text{right2} = a_{n-i+2}$（这里对称位置的右邻居）。

实际上正确考虑边界： 我们有两种可能的排列：

1. $(a_i, a_{n-i+1})$ 保持原顺序
2. 交换后顺序为 $(a_{n-i+1}, a_i)$

考虑它们对扰动的贡献变化：

• 原来可能已经存在 $a_{i-1}=a_i$ 或 $a_i=a_{i+1}$
• 交换后变为 $a_{i-1}=a_{n-i+1}$ 或 $a_{n-i+1}=a_{i+1}$
• 对右半部分也有类似对称的四个关系。

实际上，我们可以只考虑前一对相邻关系 $a_{i-1}$ 与当前第一个元素 以及 当前第二个元素与 $a_{n-i+2}$（右邻居），因为其它相邻关系在另一边的决策中已覆盖或对称。

但标程给出的简化思路是：

四种情况判断

1. 情况1： $a_{i-1}=a_i$ 且 $a_{n-i+2}=a_{n-i+1}$

   • 无论交换与否，这两对等值关系至少保留一个，交换可能减少某个，但总体不会变少吗？需要验证。

2. 情况2： $a_{i-1}=a_i$ 但 $a_{n-i+2} \neq a_{n-i+1}$

   • 不交换时，左边有一对相同。交换后，左边 $a_{i-1}$ 与 $a_{n-i+1}$ 比较。
     如果 $a_{n-i+1} = a_{i-1}$，左边仍然相同，否则左边少一个相同对。右边原来不同，交换后右边 $a_{n-i+2}$ 与 $a_i$ 比较， $a_i$ 可能等于 $a_{n-i+2}$ 吗？不保证。
     所以不一定改善，但实际标程结论是：如果 $a_{i-1}=a_i$ 或 $a_{n-i+2}=a_{n-i+1}$，则交换至少不会更差。

3. 情况3： $a_{i-1} \neq a_i$ 且 $a_{n-i+2} = a_{n-i+1}$

   • 对称情况，交换至少不会更差。

4. 情况4： 两边都不相等

   • 交换可能使某一边相等，但也可能使另一边相等，需要具体看值。
     但标程结论是：如果左边当前不等、右边当前不等，交换可能产生新相等，也可能消除，但我们可以通过尝试选最优。

最终数学结论：

• 如果 $a_{i-1} = a_i$ 或 $a_{n-i+1} = a_{n-i+2}$（注意这里的右邻居标号是 $n-i+2$，但原文写的是 $a[n-i+2]=a[n-i+1]$，即右边相邻相等），那么交换 $a_i$ 和 $a_{n-i+1}$ 后，总扰动不会增加。
• 所以最优策略是：对每个 $i$ 从 $2$ 到 $\lfloor n/2 \rfloor$（对应位置 $i$ 和 $n-i+1$），如果当前 $a_{i-1}=a_i$ 或 $a_{n-i+1}=a_{n-i+2}$，就交换 $a_i$ 与 $a_{n-i+1}$。

这样，我们贪心地消除所有可以通过对称交换消除的相邻相等对。

算法步骤

1. 读入 $n$ 和数组 $a$（1-indexed）。
2. 对 $i = 2$ 到 $\lfloor n/2 \rfloor$：
   • 如果 $a_{i-1} = a_i$ 或 $a_{n-i+1} = a_{n-i+2}$，则交换 $a_i$ 与 $a_{n-i+1}$。
3. 计算最终数组的扰动：$\text{ans} = \sum_{j=1}^{n-1} [a_j = a_{j+1}]$。
4. 输出 $\text{ans}$。

复杂度分析

• 每个测试用例 $O(n)$。
• 总 $n$ 不超过 $2\times 10^5$，可过。

示例验证

以第一个样例为例：
初始：$[1,1,1,2,3]$
$i=2$：$a_1=1,a_2=1$ 相等，交换 $a_2=1$ 与 $a_4=2$ → $[1,2,1,1,3]$
$i=3$ 已超过 $\lfloor 5/2\rfloor=2$，停止。
扰动：相邻 $1=2?$ 否，$2=1?$ 否，$1=1?$ 是，$1=3?$ 否 → 1 对。符合输出。