/ WHOJ / 题库 /

奶牛排队

奶牛排队

题目描述

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

格式

输入格式

输入第 11 行一个整数 nn,表示奶牛的个数。

输入第 22nn 个整数 a1,a2ana_1,a_2,…… a_n,分别表示每头奶牛的身高。

输出格式

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

样例1

样例输入1

3
12 8 3

样例输出1

样例解释

首先将身高为 121288 的奶牛,此时 FJ 需要分别给两头奶牛各 11 颗糖果,FJ 总共付出了 22 颗糖果;然后再交换身高为 121233 的奶牛,此时 FJ 需要给身高为 1212 的奶牛 22 颗糖果,因为它是第 22 次被交换,给身高为 33 的奶牛 11 颗糖果,这一次交换 FJ 付出了 33 颗糖果;最后交换身高为 8833 的奶牛,这时候需要分别它们各自 22 颗糖果,因为这两头奶牛都是第 22 次被交换,这一次交换 FJ 付出了 44 颗糖果。这样 FJ 总共付出的糖果数是 99

来源

地址:Online Judge\text{Online~Judge}
作者:hoogyhoogy
模拟赛T4T4