扭曲的排列

时间限制：1 秒
内存限制：256 MB
输入：标准输入
输出：标准输出

题目描述

Jerry 得到了一个由 $1$ 到 $n$ 的整数构成的排列。不幸的是，在此之前 Rick 已经对这个排列进行了“改进”，现在它不断地寻找更好的自己，这让 Jerry 感到害怕。

对于一个排列 $a$，其中逆序对（即满足 $i < j$ 且 $a_i > a_j$ 的索引对 $(i,j)$）的数量越少，我们就认为这个排列越“好”。为了找到最好的自己，这个排列每秒都会循环左移 $1$ 位，即变为：

$$ a^{\gets 1} = [a_2, a_3, \ldots, a_n, a_1] $$

请确定经过多少秒后，这个排列会变成最好的自己，即包含最少的逆序对数量。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——排列的长度。
第二行包含 $n$ 个不同的整数 $a_i$（$1 \le a_i \le n$），表示当前排列的元素。

输出格式

输出一个整数——使得排列包含最少逆序对所需的秒数。如果有多个可能的答案，输出任意一个小于 $n$ 的值。

样例

样例输入 1

3
2 1 3

样例输出 1

0

样例输入 2

5
5 3 4 2 1

样例输出 2

3