题目描述

FJ 家的 $n$ 头奶牛在排成一列准备去牧场，FJ 现在他想把这些奶牛按身高非递减的顺序排成一列。奶牛们很懒，每次只愿意和相邻的奶牛交换位置，并且还需要给奶牛一些糖果，具体方式是：如果该头奶牛是第一次被交换，那么该奶牛将获得 $1$ 颗糖果，如果是第 $2$ 次被交换就获得 $2$ 颗糖果，以此类推，当该奶牛是第 $t$ 次被交换时就会获得 $t$ 颗糖果。那么当所有奶牛完成了 FJ 要求的排列时，FJ 需要付出的糖果至少是多少？

格式

输入格式

输入第 $1$ 行一个整数 $n$，表示奶牛的个数。

输入第 $2$ 行 $n$ 个整数 $a_1,a_2，…… a_n$，分别表示每头奶牛的身高。

输出格式

输出一行一个整数表示 FJ 需要付出的糖果数。

样例1

样例输入1

3
12 8 3

样例输出1

9

样例解释

首先将身高为 $12$ 和 $8$ 的奶牛，此时 FJ 需要分别给两头奶牛各 $1$ 颗糖果，FJ 总共付出了 $2$ 颗糖果；然后再交换身高为 $12$ 和 $3$ 的奶牛，此时 FJ 需要给身高为 $12$ 的奶牛 $2$ 颗糖果，因为它是第 $2$ 次被交换，给身高为 $3$ 的奶牛 $1$ 颗糖果，这一次交换 FJ 付出了 $3$ 颗糖果；最后交换身高为 $8$ 和 $3$ 的奶牛，这时候需要分别它们各自 $2$ 颗糖果，因为这两头奶牛都是第 $2$ 次被交换，这一次交换 FJ 付出了 $4$ 颗糖果。这样 FJ 总共付出的糖果数是 $9$。

来源

地址：$\text{Online~Judge}$
作者：$hoogy$
模拟赛$T4$