J4 例题-11 分发糖果

题目描述**

老师想给孩子们分发糖果，有 $N$ 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分 $A_i$。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

​ - 每个孩子至少分配到 $1$ 个糖果。 ​ - 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

输入格式

两行

第一行，一个整数 $N$，表示还是孩子的个数。

第二行，$N$ 个整数，表示孩子的评分。

输出格式

一行，一个整数，表示老师至少需要准备的糖果数量。

样例输入

3
1 2 2

样例输出

4

样例分析

你可以分别給第一个、第二个、第三个孩子分发 $1$、$2$、$1$ 颗糖果。

数据范围

对于$100\%$ 的数据，$2 \le n \le 2\times 10^4,-10^5 \le A[i] \le 10^5$。