题目描述

小 D 有一个长为 $n$ 的序列 $(a_i)_{i=0}^{n-1}$。

小 D 可以花费 $1$ 的代价交换序列中的相邻两个元素。小 D 希望花费最少的代价使序列变得单峰。

单峰的定义为存在 $k \in [0,n)$ 满足：

1. $\forall\ 0 \le i < k,\ a_i \le a_{i+1}$；
2. $\forall\ k < i < n,\ a_i \le a_{i-1}$。

你需要求出这个最小代价。

输入格式

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

第二行 $n$ 个整数，表示序列的元素。

输出格式

输出使序列变成单峰的最小代价。

样例一

输入

4
1 2 1 3

输出

1

解释

一次交换即可使序列变为 $(1,2,3,1)$。

样例二

输入

10
5 6 8 9 4 7 1 5 4 1

输出

4

解释

序列变为 $(5,6,8,9,7,5,4,4,1,1)$。

数据范围

对于所有数据，保证 $1 \le n \le 10^6$，$1 \le a_i \le n$。