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

题目描述

一群孩子站成一排，每个孩子都有一个评分。

老师准备给这些孩子分发糖果，并且需要满足以下规则：

1. 每个孩子至少分到 1 颗糖果；
2. 如果一个孩子的评分比相邻的孩子更高，那么他必须比这个相邻的孩子分到更多糖果。

现在给定所有孩子的评分，请你计算： 在满足上述规则的前提下，老师最少需要准备多少颗糖果。

输入格式

第一行输入一个整数 n，表示孩子的数量。

第二行输入 n 个整数，第 i 个整数表示第 i 个孩子的评分 a[i]。

输出格式

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

输入输出样例 #1

输入 #1

3
1 0 2

输出 #1

5

样例解释 #1

可以给三个孩子分别分发：

2 1 2

总共需要 5 颗糖果。

输入输出样例 #2

输入 #2

3
1 2 2

输出 #2

4

样例解释 #2

可以给三个孩子分别分发：

1 2 1

第三个孩子虽然评分与第二个孩子相同，但题目只要求“评分更高”的孩子获得更多糖果，因此该分配满足要求。

数据范围

对于所有测试数据：

• 1 ≤ n ≤ 2 × $10^4$
• 0 ≤ a[i] ≤ 2 × $10^4$