时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小时候我们都喜欢玩积木。这里的积木都是单位边长的正方体块，多个积木可以堆成一个“高木”，“高木”的高度就是叠放的积木块个数。多个“高木”形成一个排列，如果高度满足先严格上升再严格下降，则称这个排列为一座山峰。严格的定义是：假设有 \(N\) 个高木从左到右排列，第 \(i\) 个高度为 \(H[i](i=1,2,……N)\)。那么如果存在一个整数 \(k∈[2,N-1]\)，使得对所有的位置 \(i\)，下式都成立，则称 \(H\) 是一座山峰。

　　　　　　\(H[i]>H[i-1] （1 < i ≤ k）\)
　　　　　　\(H[i]>H[i+1] （k < i ≤ N）\)

　　现在你有一个超级工具，每次操作可以给一段连续的区间各位置都叠放上一块积木，使得高度同时增加1个单位，现在有一个“高木”排列，需要将其改造为一座山峰，只允许使用这种超级工具，最少需要操作几次可以达到这个目标呢？假设积木无限供应。

【输入格式】

　　第一行包含一个整数 \(N\)，为上文提到的初始排列中“高木”的个数。
　　第二行包含 \(N\) 个正整数，表示由左到右的 \(N\) 个位置“高木”的初始高度 \(H[i]\)，数字由空格隔开。

【输出格式】

　　输出包含一个整数，表示所需要的最少的操作次数。

【输入输出样例】

　Input

6
3 4 3 6 7 8

　Output

2

【数据限制】

　　对于 \(30\%\) 的数据，\(3≤N≤20\)，\(0<H[i]≤50\)
　　对于 \(50\%\) 的数据，\(3≤N≤100\)，\(0<H[i]≤1000\)
　　对于 \(100\%\) 的数据，\(3≤N≤10^5\)，\(0<H[i]≤10^7\)

【来源】

　　Mr.he**