P14419 [JOISC 2014] 有趣的家庭菜园 / Growing Vegetables is Fun

热爱家庭园艺的 JOI 君每年都会在自家的田地里种植一种名为 IOI 草的植物。JOI 君的田地被划分为东西方向排列的 $N$ 个区域，从西侧开始依次编号为 $1$ 至 $N$。每块区域种植一株 IOI 草，共 $N$ 株。第 $i$ 块区域种植的 IOI 草在春季会长到高度 $h_i$，此后便不再生长。 春天，JOI 君去查看田地时，发现 IOI 草的布局与预想不同。由于 IOI 草是喜光植物，若某块区域种植的 IOI 草，在编号比它小的区域或编号比它大的区域中，存在比它更高的 IOI 草，则该草会在夏季来临前枯萎。换言之，为了确保所有 IOI 草都不枯萎，必须满足以下条件： - 对于所有满足 $2 \le i \le N - 1$ 的整数 $i$，以下两个条件中至少有一个成立： - 对于所有满足 $1 \le j \le i - 1$ 的整数 $j$，有 $h_j \le h_i$。 - 对于所有满足 $i + 1 \le k \le N$ 的整数 $k$，有 $h_k \le h_i$。 由于 IOI 草价值昂贵，且植株高大、枝叶纤细，JOI 君一次只能交换相邻的两株 IOI 草。也就是说，一次操作中，JOI 君可任意选择区域 $i$（$1 \le i \le N - 1$），并交换区域 $i$ 和区域 $i + 1$ 的 IOI 草。由于夏季将至，枯萎风险升高，JOI 君希望知道使所有 IOI 草都不枯萎所需的最少操作次数。 **问题** 当给定 JOI 君田地的区域数量，以及每株 IOI 草的高度信息时，请编写程序，求出为使所有 IOI 草都不枯萎所需的最少交换次数。

从标准输入读取以下数据： - 第 $1$ 行包含一个整数 $N$，表示 JOI 君田地的区域数量。 - 接下来的 $N$ 行包含关于 IOI 草高度的信息。其中第 $i$ 行（$1 \le i \le N$）包含一个整数 $D_i$，表示在区域 $i$ 种植的 IOI 草在春季时的高度。

向标准输出输出一行，包含一个整数，表示使所有 IOI 草都不枯萎所需的最少操作次数。

### 样例 1 解释 :::align{center}  配图来自 [LibreOJ](https://loj.ac/p/2873) ::: ### 数据范围 所有输入数据均满足以下条件： - $3 \le N \le 300000$。 - $1 \le D_i \le 1000000000$。 ### 子任务 **子任务 1 [10 分]** - 满足 $N \le 8$。 **子任务 2 [20 分]** - 满足 $N \le 20$。 **子任务 3 [15 分]** - 满足 $N \le 5000$。 **子任务 4 [55 分]** 无额外限制。 翻译由 Qwen3-235B 完成