5245：P8613 [蓝桥杯 2014 省 B] 小朋友排队
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：0
解决：0
题目描述
# P8613 [蓝桥杯 2014 省 B] 小朋友排队
## 题目信息
- 题号：P8613
- 标题：[蓝桥杯 2014 省 B] 小朋友排队
- 难度：普及+/提高
- 标签：贪心, 2014, 树状数组, 前缀和, 蓝桥杯省赛
- 时间限制：1.00s
- 内存限制：128.00MB
- 提交数：5775
- 通过数：1412
## 题目描述
$n$ 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是 $0$。
如果某个小朋友第一次被要求交换，则他的不高兴程度增加 $1$，如果第二次要求他交换，则他的不高兴程度增加 $2$（即不高兴程度为 $3$），依次类推。当要求某个小朋友第 $k$ 次交换时，他的不高兴程度增加 $k$。
请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。
## 输入格式
输入的第一行包含一个整数 $n$，表示小朋友的个数。
第二行包含 $n$ 个整数 $H_1,H_2 \cdots H_n$，分别表示每个小朋友的身高。
## 输出格式
输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。
## 输入输出样例
### 输入 #1
```text
3
3 2 1
```
### 输出 #1
```text
9
```
## 说明/提示
【样例说明】
首先交换身高为 $3$ 和 $2$ 的小朋友，再交换身高为 $3$ 和 $1$ 的小朋友，再交换身高为 $2$ 和 $1$ 的小朋友，每个小朋友的不高兴程度都是 $3$，总和为 $9$。
【数据规模与约定】
对于 $10\%$ 的数据，$1 \le n \le 10$；
对于 $30\%$ 的数据，$1 \le n \le 1000$；
对于 $50\%$ 的数据，$1 \le n \le 10000$；
对于 $100\%$ 的数据，$1 \le n \le 100000$，$0 \le H_i \le 1000000$。
时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛