[Baltic2007]Ranklist sorting名次排序问题

已知所有参赛选手的得分，你需要通过移动选手，将选手按照得分从高到低排序。

保存选手信息的数据结构仅支持一种操作：将一名选手从位置 $i$ 移动到位置 $j$，且不改变其他选手之间的相对顺序。具体而言：

• 若 $i>j$，则原先位于位置 $j$ 至位置 $i-1$ 的选手均向后移动一个位置；
• 若 $i<j$，则原先位于位置 $i+1$ 至位置 $j$ 的选手均向前移动一个位置。

位置编号从 $1$ 开始，一次移动操作的代价为 $i+j$。

请确定一种移动方案，使所有选手按照得分从高到低排列，并使移动过程的总代价最小。如果有多种方案的总代价均为最小值，则选择其中移动次数最少的方案。

输入格式

第一行输入一个整数 $n$，表示参赛选手的人数。

接下来 $n$ 行，每行输入一个非负整数 $S_i$，表示一名选手的得分。所有选手的得分互不相同。

输出格式

输出一行一个整数，表示在总代价最小的前提下，所需的最少移动次数。

样例输入

5
20
30
5
15
10

样例输出

2

数据范围

• $2\le n\le 10^3$；
• $0\le S_i\le 10^6$；
• 所有选手的得分互不相同。

来源与许可

本题为 Baltic 2007 试题「Ranklist Sorting（名次排序问题）」，题面与测试数据整理自 BZOJ。

样例 1

输入

5
20
30
5
15
10

输出

2