题目限制

1000 ms 128 M

题目描述

小A拥有一个奶牛场，奶牛场有N头奶牛分别饲养在编号为1--N的牛棚。这些奶牛比较聪明，如果体重较大的奶牛发现其左右相邻的牛棚中的奶牛比它体重小却喂了更多的饲料，这只体重较大的奶牛就会不开心从而拒绝产奶。

为此，小A决定喂养奶牛时按照以下标准：

1、每头奶牛最少要喂1单位饲料。

2、相邻且体重较大的奶牛必须喂更多单位的饲料。

请问小A最少需要为聪明的奶牛们准备多少单位的饲料？

输入格式

第一行一个整数N，表示奶牛数，其中0＜N≤50000；

第二行N个数表示每一头奶牛的体重，用空格隔开，每个数不超过50000。

输出格式

输出一个数，表示最少需要准备的饲料数量

数据范围

对于5%的数据，0＜N≤10；

对于30%的数据，0＜N≤2000；

对于100%的数据，0＜N≤50000。

输入样例

input1:

3

1 2 2

input2:

5

1 2 3 4 5

input3:

7

2 2 1 3 5 5 3

输出样例

output 4

output 15

output 12

样例解释

一共有3头奶牛，它们的体重分别是1 2 2

那么最少需要喂的饲料数量为1+2+1=4