题意理解

我们有 $N$ 株草，高度为 $h_i$，种在 $N$ 个位置（从左到右编号 $1 \dots N$）。

要求：
对于任意一株草（除了最左和最右），不能出现它左边有比它高的草并且它右边也有比它高的草。
换句话说，任何一株草不能同时“夹在”两株比它高的草之间。

等价条件：
最终排列必须是一个单峰序列（先非严格递增到峰值，然后非严格递减），或者是一个完全递增/完全递减序列。

允许的操作：
只能交换相邻的两株草。

目标：
求最少交换次数。

关键观察

1. 最终排列形态
   最终排列中，所有相同高度的草应该连续排列，并且整体是一个单峰形状。
   因为如果相同高度的草分散开，可能会被更高的草夹在中间而枯萎。

2. 相同高度的草之间的相对顺序
   在最优解中，相同高度的草在最终排列中的相对顺序与原序列相同（稳定排序），因为交换相同高度的草不会改变枯萎情况，但会增加不必要的交换次数。

3. 问题转化
   我们要把原序列通过相邻交换变成单峰序列，且相同高度的草保持原顺序。
   这等价于：

   • 把原序列按高度分组，每组内顺序固定。
   • 把这些组排列成单峰形状，组内成员连续。
   • 计算从原序列变成这个目标序列的相邻交换次数。

4. 交换次数计算
   相邻交换次数 = 原序列到目标序列的逆序对数（考虑目标序列中每个元素的位置）。

贪心策略

我们可以这样构造目标序列：

• 把所有草按高度分组，相同 $h$ 的为一组。
• 对于每一组，我们要决定它们放在“峰”的左边（递增部分）还是右边（递减部分）。
• 对于高度 $h$，设它在原序列中的位置集合为 $p_1, p_2, \dots, p_k$（升序）。
• 如果我们把它们全部放在左边（递增部分），那么它们在目标序列中的位置是连续的一段，并且为了保持组内原顺序，它们在目标序列中的位置也是按 $p$ 升序排列。
• 如果我们把它们全部放在右边（递减部分），那么它们在目标序列中的位置也是连续的一段，但组内顺序仍然是 $p$ 升序（因为递减部分相同高度也是非严格递减，即相等时保持原序）。

最优放置规则

对于高度 $h$ 的一组，设它们原位置的中位数（或某个中心位置）为 $m$。
如果 $m$ 在全局中位数（位置 $(N+1)/2$）的左边，则这一组放在左边递增部分更优；否则放在右边递减部分更优。

这样做的直观原因：
每个元素的目标位置应尽量靠近原位置，以减少总移动距离（相邻交换次数 ≈ 元素移动距离之和）。

算法步骤（文字描述）

1. 按高度从低到高处理（因为低草不会影响高草的枯萎情况）。
2. 对于每个高度，确定它应该放在峰左还是峰右：
   • 计算该高度组在原序列中的位置中位数。
   • 比较中位数与全局中位数位置，决定放左/右。
3. 分配目标位置：
   • 左边部分：按高度升序，同高度按原顺序，从左到右分配位置。
   • 右边部分：按高度升序，同高度按原顺序，从右到左分配位置。
4. 得到目标排列后，计算原序列到目标序列的逆序对数（因为相邻交换次数 = 逆序对数）。

样例验证

样例 1
输入：

6
2
8
4
5
3
6

原序列：[2, 8, 4, 5, 3, 6]
按规则构造目标序列（单峰），计算逆序对得到 3，与输出一致。

样例 2
输入：

5
4
4
2
4
4

原序列：[4, 4, 2, 4, 4]
构造目标序列，计算交换次数为 2。

样例 3
输入：

4
1
3
4
2

原序列已经满足条件（单峰：1 3 4 2），交换次数 0。

结论

这个问题本质是带稳定约束的单峰排序最小相邻交换问题。
通过贪心分组 + 中位数决策 + 逆序对计算，可以得到最优解。
时间复杂度主要由逆序对计算部分决定，可用树状数组/归并排序在 $O(N \log N)$ 内完成。