7

破解了符文之语，小FF开启了通往地下的道路。当他走到最底层时，发现正前方有一扇巨石门，门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“神的殿堂”。小FF猜想里面应该就有王室的遗产了。但现在的问题是如何打开这扇门……

仔细研究后，他发现门上的图案大概是说：古代人认为只有智者才是最容易接近神明的。而最聪明的人往往通过一种仪式选拔出来。仪式大概是指，即将隐退的智者为他的候选人写下一串无序的数字，并让他们进行一种操作，即交换序列中相邻的两个元素。而用最少的交换次数使原序列变成不下降序列的人即是下一任智者。

小FF发现门上同样有着n个数字。于是他认为打开这扇门的秘诀就是找到让这个序列变成不下降序列所需要的最小次数。但小FF不会……只好又找到了你，并答应事成之后与你三七分……

输入格式: 第一行为一个整数n，表示序列长度

第二行为n个整数，表示序列中每个元素。

输出格式: 一个整数ans，即最少操作次数。

输入样例: 4 2 8 0 3 输出样例: 3 说明/提示: 对于30的数据1≤n≤10 4 。

对于100的数据1≤n≤5∗10 5 ；

−maxlongint≤A[i]≤maxlongint。

样例说明：开始序列为2803，目标序列为0238，可进行三次操作的目标序列：

1．Swap (8,0):2 0 8 3

2．Swap (2,0):0 2 8 3

3．Swap (8,3):0 2 3 8

思路：就是求解逆序对的个数 1.什么是逆序对呢？ （对当前这个数，右边的数比他小，则构成一个逆序对） 例如 5 2 4 6 2 3 2 6 我们从左到右来看 对5 来说，右边比他小的有5个 2 4 2 3 2，所以对5来说 逆序对有5个 2，右边比2小的 0个 ，逆序对0个 4，右边比4小的3 个 ，2 3 2，逆序对3个 6，右边比6小的3个， 2 3 2，逆序对3个 2，逆序对0个 3，右边比3小的1个，6 ，逆序对1个 2，逆序对0个 6，逆序对0个 所以总的逆序对个数 12个。

2.本题中 ，逆序对个数是3 所以交换三次 为什么根据逆序对的个数 得到交换次数呢？ 本题中开始为2 8 0 3 我们从大到小找逆序对， 8，逆序对2 3，逆序对0 2，逆序对1 0，逆序对0

对于8，要到最大值位置，需要交换2 次 ，数组变成 2 0 3 8 对于3，现在处于第二大的位置，交换0次，数组为 2 0 3 8 对于2，要到最大值位置，需要交换1次，数组变成 0 2 3 8 对于0，现在处于第四大的位置，交换0次，数组为0 2 3 8 所以可得 逆序对的个数，即为交换次数

3.如何求逆序对呢？ 使用分治法，也就是归并排序中改变一下就可以得到逆序对的个数 如 对 2 8 0 3 第一次排序左边2 8 可得逆序对0个 第二次排序右边0 3 可得逆序对0个 第三次排序左＋右2 8 0 3，可得逆序对3个

4.归并排序如下：