该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

打开宝箱后，小Z欣喜若狂，这不就是他梦寐以求的机械键盘吗，他太开心了，他要跟小伙伴们分享今天的喜悦，他决定邀请今天帮助过他的小伙伴举行欢庆会，他打算为这些小伙伴们准备一些蛋糕，$\red{n}$个小伙伴站成一排，每个小伙伴都有一个贡献值$\red{ai}$，也就是今天对他的帮助程度，他将按照一下规则，对小伙伴进行分发蛋糕：

1）每个小伙伴至少分到$\red{1}$个蛋糕

2）相邻的两个小伙伴$\red{贡献值更高}$的会获得更多的蛋糕

你能够帮他算一下$\red{最少}$需要多少块蛋糕吗？

输入格式

共$\red{n+1}$行

第一行一个正整数$\red{n}$表示参加庆功会的小伙伴的人数

第二行为$\red{n}$个数分别表示每个人的贡献值，用空格隔开

输出格式

共一行为一个正整数$\red{s}$，表示最少的蛋糕数

样例

输入数据1

3
1 0 2

输出数据1

5

输入数据2

3
1 2 2

输出数据2

4

提示

数据范围与提示

对于$\red{输入样例1}$，贡献值分别为$\red{1 ， 0 ，2}$

由于每个孩子至少有一块蛋糕，所以三个人出示蛋糕数为$\red{1 ，1 ， 1}$

第一个人的贡献值大于第二个人，所以一个人的蛋糕数会比第二人多，最少为$\red{2}$块。第二个人比相邻人都小，故第二人为$\red{1}$块蛋糕，第三人比第二人贡献值大，所以第三人的蛋糕数比第二人多，最小为$\red{2}$块。

分别给第一个、第二个、第三个孩子分发$\red{2、1、2}$ 块蛋糕。

对于 $\red{20\%}$的数据$\red{1 <= n <= 100, 0<=ai<=100}$

对于$\red{50\%}$的数据$\red{1 <= n <= 1000, 0<=ai<=1000}$

对于$\red{100\%}$的数据$\red{1 <= n <= 20000, 0<=ai<=20000}$