No submission language available for this problem.

Background (错题)

宗门不定时的会进行修墙比赛，来考察弟子们的灵力操控的能力，来奖励比较努力和优秀的弟子，给他们倾向更多的资源。关小山想着能够获得更多的资源帮助自己进行修炼，也就参加了。

Description

为了方便修墙比赛的描述，墙面都是一块块同等大小的砖块砌成的，并且放在大家面前的都是一模一样参差不齐的墙面。每列的高度可以记为砖块的个数。只需要按规则以最快的办法修缮成从两边依次严格递减即可。即如：3 2 2 3 1 修缮成 3 4 5 3 1 ，墙体从 5 开始往两边递减。

修缮的规则如下：

• 只能够在一个连续的区间叠加 1 层砖块，一次叠加表示一次操作
• 修缮的最后需要在墙体中找到一个最高位，往两边严格递减。

设整个墙体序列为 $A_1, A_2, A_3, ... , A_k, A_{k+1} ,..., A_{n-1}, A_{n}$，即存在一个 $A_k$ 是最大的，$A_{1,2,3,...,k}$ 严格递增，$A_{k,k+1, ..., n-1, n}$ 严格递减。

关小山希望赢得比赛，请问他最少需要操作多少次？

本题友好地不做多组测试

Format

Input

第一行一个整数 n，表示墙体的列数

第二行有 n 个整数表示每列墙体的高度。

Output

一行一个整数表示最少的操作次数

Samples

5
3 2 2 3 1

3

5
9 7 5 3 1

0

2
2021 2021

1

8
12 2 34 85 4 91 29 85

93

Limitation

样例 1 解释

• 对 [2,5] 进行操作，序列变为 {3,3,3,4,2}。
• 对 [2,3] 进行操作，序列变为 {3,4,4,4,2}。
• 对 [3,3] 进行操作，序列变为 {3,4,5,4,2}。

样例 2 解释

序列已经满足要求，不需要操作。

样例 3 解释

对区间 [1,1][1,1] 或 [2,2][2,2] 进行操作都可。

测试数据

对于 100% 的数据，1 ≤ N ≤ 2×$10^5$ ，1 ≤ $A_i​$ ≤ $10^9$。