题目描述

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

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

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

你能够帮他算一下最少需要多少块蛋糕吗？

输入格式

共 $\red{n +1}$行

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

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

输出格式

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

样例

输入数据1

3
1 0 2

输出数据1

5

输入数据2

3
1 2 2

输出数据2

4

提示

数据范围与提示

对于输入样例1，贡献值分别为1，0，2

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

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

分别给第一个、第二个、第三个孩子分发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}$