[传智杯 #2 初赛] 1024 程序员节发橙子
题目描述
每年的 1024 程序员节日,黑马程序员都会举办大型的庆祝活动。今年的程序员节也不例外,每个班级的同学都发了橙子。
班级里有 $n$ 名同学从前到后排成一排,且已经得知了这些同学的成绩,其中第 $i$ 名同学的成绩是 $a_i$。班主任想根据同学们上个阶段的考试成绩来评定发橙子的数量。为了激励成绩优秀同学,发橙子时需要满足如下要求:
- 相邻同学中成绩好的同学的橙子必须更多。若相邻的同学成绩一样,则它们分到的数量必须平等。
- 每个同学至少分配一个橙子
由于预算有限,班主任希望在符合要求的情况下发出尽可能少的橙子。请问,至少需要准备多少橙子呢?
输入输出格式
输入格式
第一行是一个整数 $n$,表示学生数量。
接下来一行有 $n$ 个整数,第 $i$ 个整数 $a_i$,表示第 $i$ 个同学的成绩。
输出格式
输出答案,也就是需要最少准备多少个橙子。
输入输出样例
输入样例 #1
5
3 4 5 4 3
输出样例 #1
9
说明
#### 样例 1 解释
每位同学拿到的橙子的数量分别是 $1,2,3,2,1$,所以至少需要准备 $9$ 个。
#### 数据规模与约定
对于全部的测试点,保证 $1 \leq n \leq 10^6$,$0 \leq a_i \leq 10^9$。