说明

青蛙又给了周欣一个长为 $N$ 的正整数序列 $A_i$，周欣可以进行若干次操作，每次可以选择一个位置 $i$，满足 $1\le i\le N-1$，将 $A_i$ 的值和 $A_{i+1}$ 的值进行交换。

设经过这若干次操作后的序列为 $B_i$，那么需要存在一个整数 $k \in [1,N]$，满足：

• 区间 $[1,k]$ 构成的子序列 $[B_1,B_2,\cdots,B_k]$ 是一个非严格单调递增的序列，即相邻两项允许相等，但是左边元素不能大于右边元素。
• 区间 $[k,N]$ 构成的子序列 $[B_k,B_{k+1},\cdots,B_N]$ 是一个非严格单调递减的序列，即相邻两项允许相等，但是左边元素不能小于右边元素。

周欣想知道至少需要对序列进行多少次上述操作后，这个要求才能得以满足，他把这个问题交给了你来解决。

输入格式

第一行一个整数 $N$，表示序列长度。

第二行 $n$ 个整数表示 $A_1,A_2,\cdots ,A_n$。

输出格式

输出一个整数，表示答案，即最少的操作次数。

样例

7
3 1 4 1 5 9 2

3

样例

9
10 4 6 3 15 9 1 1 12

8

样例

8
9 9 8 8 7 7 6 6

0

提示

数据范围

对于 $20\%$ 的数据，满足 $n \leq 10$。

对于 $50\%$ 的数据，满足 $n \leq 5\,000$。

对于 $100\%$ 的数据，满足 $1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^5$。