小金太开心了，他要跟小伙伴们分享今天的喜悦，他决定邀请今天帮助过他的小伙伴举行欢庆会，他打算为这些小伙伴们准备一些蛋糕，n个小伙伴站成一排，每个小伙伴都有一个贡献值 ai，也就是今天对他的帮助程度，他将按照一下规则，对小伙伴进行分发蛋糕：
1）每个小伙伴至少分到1个蛋糕
2）相邻的两个小伙伴贡献值更高的会获得更多的蛋糕
你能够帮他算一下最少需要多少块蛋糕吗？

共 n+1行
第一行一个正整数 n表示参加庆功会的小伙伴的人数
第二行为 n个数分别表示每个人的贡献值，用空格隔开

共一行为一个正整数 s，表示最少的蛋糕数

样例一解释：


对于样例1，贡献值分别为 1，0，2
由于每个孩子至少有一块蛋糕，所以三个人出示蛋糕数为 1，1，1
第一个人的贡献值大于第二个人，所以一个人的蛋糕数会比第二人多，最少为 2块。第二个人比相邻人都小，故第二人为 1块蛋糕，第三人比第二人贡献值大，所以第三人的蛋糕数比第二人多，最小为 2块。
分别给第一个、第二个、第三个孩子分发 2、1、2 共计 5块蛋糕。


样例二：
输入：
3
1 2 2
输出：
4
样例二解释：
对于贡献值1 2 2，一开始每人一块即1 1 1，第一人贡献小于第二人蛋糕数不变依然是1块，第二人比第一人贡献值高蛋糕数在原来基础上增加一块即2块，第三人贡献不比周围人大依然是1块。最后每人手上的蛋糕数分别是1 2 1，共计4块蛋糕


对于 20%的数据 1<=n<=100,0<=ai<=100
对于 50%的数据 1<=n<=1000,0<=ai<=1000
对于 100%的数据 1<=n<=20000,0<=ai<=20000

动态规划 信息未来