题目描述

传奇的“四骑士”正在为演出准备一个名为“永动机”的魔术。为了实现它，他们制造了一套机械装置：$n$ 个齿轮排成一行，齿数分别为 $a_1,a_2,\ldots,a_n$。

不幸的是，装置没有按预期工作，因此骑士们开始寻找问题。经过几个不眠之夜和漫长而复杂的计算，他们发现齿轮的排列顺序不对：正确的装置应当满足，当最左边的第一个齿轮以某个固定速度转动时，最右边的最后一个齿轮转动得尽可能快。

距离演出已经没有多少时间，而把装置拆开再重新组装需要很久。幸运的是，魔术师灵巧的双手可以很快地交换两个相邻齿轮的位置，因此装置仍然能够修好。经过长时间的排查，骑士们已经非常疲惫，希望尽快去休息，为演出做准备。请你求出修好装置所需的最少交换次数。

输入格式

第一行包含一个整数 $n$（$2\le n\le 2\cdot 10^5$），表示齿轮的数量。

第二行包含 $n$ 个整数 $a_i$，第 $i$ 个数表示第 $i$ 个齿轮的齿数（$2\le a_i\le 10^{18}$）。

输出格式

输出一个整数，表示修好装置所需的最少交换次数。

5
3 7 2 2 4

2

7
2 8 2 2 8 3 4

4

8
9 10 5 4 5 7 7 2

1