UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1341. [Baltic2007]Ranklist sorting名次排序问题

统计 下载数据

Description

已知参赛选手的得分,你的任务是按照得分从高到底给出选手的排名。遗憾的是,保存选手信息的数据结构只支持
一种操作,即将一个选手从位置i移动到位置j,该移动不改变其他选手的相对位置,即如果i>j,位置j和位置i-1
之间的选手的位置都比原来加1,相反如果i<j,则位置i+1和位置j之间的选手的位置都比原来减一。上述移动的操
作的代价定义为i+j,这里,位置编号从1开始。请你编程确定一个移动选手的步骤,将选手按照得分从高到低排序
,并使整个移动过程的代价最小。

Input

第一行为一个整数n(2<=n<=1000),表示选手的人数;
接下来的n行,每行一个非负整数Si( 0<=Si<=1000000),表示一个选手的得分。你可以认为每人的得分是不同的。

Output

第一行为一个整数,表示移动的次数

Sample Input

5
20
30
5
15
10

Sample Output

2

Hint

Source