U460954 多边形的表示方法

嘿！熊 sir 要来检查暑假作业了，各位……都写完了吗？

我们都知道几何中多边形的表示方法： 从任意一个点开始，顺时针或逆时针写出每一个点所对应的字母。 但是，你苛刻的数学老师（不是熊sir）不仅要检查你的表示方法是否正确，他还要求你让这个字母串尽可能的有序，即逆序对尽可能的少。 但是班上的同学日理万鸡，根本没工夫处理这一点小事，他们把这个任务外派给了你 **形式化地：给定一个有点权的环，求一种展开成链的方式使链中的逆序对数量最少（展开后可以翻转整个链）**

为了避免繁杂的字符串操作，第 $i$ 个点有一个数字编号 $D_i$，请根据数字编号判断逆序对、输出表示方案。 第一行，输入 $n$，表示你需要处理一个 $n$ 边形（当然，这个 $n$ 边形有 $n$ 个顶点） 第二行，输入 $n$ 个整数，用空格隔开，表示这个多边形的一种表示方法

一行，输出一个整数，表示最优表示方案中逆序对的数量

### 逆序对的定义 对于一种表示方案中的第 $i$ 个点和第 $j$ 个点，如果 $$ i < j\ \ 且\ \ D_i > D_j $$ 则称 $i$ 与 $j$ 之间存在一个逆序对 ### 数据范围 对于 $15\%$ 的数据，$n \leq 400$。 对于 $40\%$ 的数据，$n \leq 1000$。 对于 $60\%$ 的数据，$n \leq 4000$。 对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^5$，$1 \leq D_i \leq 10^9$。