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

投喂修狗

题目描述

小明家里有n只修狗，小明想投喂一下这些修狗，要保证每只狗都被喂过，于是让它们在客厅里面站成一排。每只修狗都有它的体积v，一般体积越大的修狗吃的粮食越多，同时修狗比较喜欢妒忌，它们会注意到自己左边第一只和右边第一只同伴的体积和被投喂的狗粮的数量，如果存在体积比自己瘦小还吃得比自己多的它就会开始大吵大闹，小明不希望看到这样的情况发生，同时小明也想尽可能的节约一点狗粮，那么请你帮忙计算一下需要的最少狗粮是多少。

输入格式

第一行一个整数N，表示修狗的数量； 第二行N个数表示修狗的体积，以空格隔开

输出格式

输出一个数，表示最少所需的狗粮数。

样例 #1

样例输入 #1

3
1 2 2

样例输出 #1

4

提示

对于20%的数据，0＜N≤10； 对于50%的数据，0＜N≤1000； 对于100%的数据，0＜N≤50000 ，v[i] <= 50000。