题目描述

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\)