题目描述

热爱家庭园艺的 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 草都不枯萎所需的最少操作次数。

6
2
8
4
5
3
6

3

5
4
4
2
4
4

2

4
1
3
4
2

0

提示

样例 1 解释

:::align{center}

配图来自 LibreOJ :::

数据范围

所有输入数据均满足以下条件：

• $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 完成