奶牛排队
题目描述
FJ
家的 头奶牛在排成一列准备去牧场,FJ
现在他想把这些奶牛按身高非递减的顺序排成一列。奶牛们很懒,每次只愿意和相邻的奶牛交换位置,并且还需要给奶牛一些糖果,具体方式是:如果该头奶牛是第一次被交换,那么该奶牛将获得 颗糖果,如果是第 次被交换就获得 颗糖果,以此类推,当该奶牛是第 次被交换时就会获得 颗糖果。那么当所有奶牛完成了 FJ
要求的排列时,FJ
需要付出的糖果至少是多少?
格式
输入格式
输入第 行一个整数 ,表示奶牛的个数。
输入第 行 个整数 ,分别表示每头奶牛的身高。
输出格式
输出一行一个整数表示 FJ
需要付出的糖果数。
样例1
样例输入1
样例输出1
样例解释
首先将身高为 和 的奶牛,此时 FJ
需要分别给两头奶牛各 颗糖果,FJ
总共付出了 颗糖果;然后再交换身高为 和 的奶牛,此时 FJ
需要给身高为 的奶牛 颗糖果,因为它是第 次被交换,给身高为 的奶牛 颗糖果,这一次交换 FJ
付出了 颗糖果;最后交换身高为 和 的奶牛,这时候需要分别它们各自 颗糖果,因为这两头奶牛都是第 次被交换,这一次交换 FJ
付出了 颗糖果。这样 FJ
总共付出的糖果数是 。
来源
地址:
作者:
模拟赛
相关
在下列训练计划中: