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

【问题描述】

老师组织一群孩子围成一个圈进行游戏，游戏结束后老师会根据每个孩子的表现进行评分并给予糖果奖励。

每个孩子只能看见与自己相邻的2个孩子(左边的和右边的)的情况，只会关心相邻的且比自己评分低的同学的糖果数(如果相邻2个孩子的评分相等，则不关心)。

为保证公平，相邻的孩子中，评分高的孩子必须获得更多的糖果(如果左右相邻2个孩子的评分相等，则不关心，即分最少的糖果1个)。

同时，为鼓励孩子的积极性，每个孩子至少都能拿到1个糖果。

现在需要你帮助老师来分发糖果，问怎么分配才能使要准备的糖果数最少?计算出需要的最少糖果数。

【输入格式】

输入文件名为candy.in。

输入有二行，第一行一个正整数 $n$ 表示孩子的个数。 第二行 $n$ 个非负整数，相邻的数用空格隔开，分别表示孩子的表现评分。

【输出格式】

输出文件名为candy.out。

一个整数，表示最少需要准备的糖果数。

输入样例1

3
1 2 0	

输出样例1

6

输入样例2

4
2 3 3 3

输出样例2

6

【数据范围】

对于$40$%的数据，$1<=n<=100$;

对于$100$%的数据，$1<=n<=100000$; 所有评分都是$0$到$100$之间的一个整数。

【样例解释】

样例一，分别分配2、3、1的糖果，所以最少需要6个糖果。

样例二，分别分配1、2、1、2的糖果，所以最少需要6个糖果。