Description

小A现在有一个长度为n的序列{xi}，但是小A认为这个序列不够优美。 小A认为一个序列是优美的，当且仅当存在k ɛ[1，n]，满足： X1<=x2<=... Xk>=xK+1>=xK+1>=...>=xn 现在小A可以进行若干次操作，每次可以交换序列中相邻的两个项，现在他想知道最少操作多少次之 后能够使序列变为优美的。

Input Format

第一行一个正整数n，表示序列的长度。 接下来一行n个整数，表示初始的序列。

Output Format

输出一行一个整数，表示最少需要的操作次数。

Sample

Sample Input

5
3 4 5 1 2

Sample Output

1

Hint

对于30%的数据，n<=12 对于60%的数据，n <= 100000, ai互不相同 对于100%的数据，n，ai<= 100000