算法思路

要把序列变为先严格递增后严格递减的单峰序列，只能对任意位置做“+1”操作，且操作次数要最少。可以分三步：

前缀严格递增预处理

令 b[j] 表示将原序列 a[1..j] 调整为严格递增时，第 j 个位置的最终值最小可能值；同时记录所需的操作次数前缀和 f[j]。 具体做法：

• 初始化 b[1] = a[1], f[1] = 0。

题目内容

多多在纸上写下了一个整数序列，他可以对任意一个数进行 $+1$ 操作，每个数的操作次数不限。

他想知道，他至少要操作多少次，可以使这个序列变成一个单峰序列。

单峰序列定义：假设序列为 $a_1,a_2,...,a_n$ ，存在一个数 $i (1 < i < n )$ ，满足 $a_1 < a_2 < a_3 … < a_i >a_{i+1}>a_{i+2}>…>a_n$ ，即这个序列先严格递增再严格递减。

输入描述

输入为两行，第一行为一个整数 $n(3≤n≤100000)$ ，表示序列长度。

第二行为 $n$ 个整数，表示序列中的数。$(1<=a_i<=10000000)$

输出描述

输出最小的操作次数

样例1

输入

3
2 2 2

输出

1