1099 : 公平

中秋节某咸鱼让ACM协会的小朋友排成一排，然后按照AC数给他们发月饼。
每个小朋友至少要拿到一个月饼。
小朋友都想被公平对待，所以如果一个小朋友的AC数比挨着的小朋友多，那他得到的月饼也必须比旁边小朋友多，不然他就会觉得不公平，然后哭鼻子。
某咸鱼很穷，你能帮她找出一个满足要求的分配方案，使得需要准备的月饼数量最少么?

PS：如果相邻两个小朋友的AC数相同，因为他们并没有被告知自己的罚时，所以并不要求月饼数量一样多。

多组输入，每组输入第一行一个正整数n，代表小朋友的数量。
第二行n个正整数a1,a2...an，以空格分割，代表每个小朋友的AC数。
Lmitis:
1<=n<=100
1<=ai<=100

对于每组输入，在一行内输出一个整数，代表需要准备的月饼数。

5
1 3 3 2 1

9