#P16157. [2022国家队训练杭州站]序列

[2022国家队训练杭州站]序列

题目描述

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

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

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

  1. ∀ 0≤i<k, ai≤ai+1\forall\ 0 \le i < k,\ a_i \le a_{i+1};
  2. ∀ k<i<n, ai≤ai−1\forall\ k < i < n,\ a_i \le a_{i-1}。

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

输入格式

第一行一个整数 nn,表示序列长度。

第二行 nn 个整数,表示序列的元素。

输出格式

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

样例一

输入

4
1 2 1 3

输出

1

解释

一次交换即可使序列变为 (1,2,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)(5,6,8,9,7,5,4,4,1,1)。

数据范围

子任务编号 n≤n \le 特殊性质 分值
1 1010 无 11
2 100100 2121
3 10610^6 aia_i 互不相同 3636
4 无 4242

对于所有数据,保证 1≤n≤1061 \le n \le 10^6,1≤ai≤n1 \le a_i \le n。