3269. 喂竹鼠

【题目描述】

小H在吃过一次烤竹鼠之后，觉得非常美味，也动了自己养殖竹鼠的心思，正好家附近有很多竹子，于是在家旁建了个养殖场，他把养殖场隔出来N个隔间并且编好了号，每个隔间内养一只竹鼠。但竹鼠的特性非常奇怪，在喂食的时候，体重较大的竹鼠如果看到，左右相邻的隔间有竹鼠比它体重更轻却喂了更多的食物，大竹鼠就会心情郁闷而影响到它的健康。

为了科学高效的养殖，小H决定喂食时遵循两个规矩：

1，每个竹鼠最少要喂1片竹子

2，相邻的竹鼠中，如果体重不同，则体重更高的竹鼠必须喂更多的竹子

请问小H最少需要为竹鼠们准备多少片竹子呢？

【输入格式】

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

第二行N个数表示不同竹鼠的体重，以空格隔开，每个数不超过50000。

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

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

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

【输出格式】

输出一个数，表示最少需要准备的竹片数

【样例输入】

input example1: 
3 
1 2 2 
input example2: 
5 
1 2 3 4 5
input example3: 
7 
2 2 1 3 5 5 3

【样例输出】

output example1: 4 
output example2: 15 
output example3: 12

【提示】

一共有3只竹鼠，它们的体重分别是1 2 2

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

【来源】