发橙子

题目描述

每年的 1024 程序员节日，黑马程序员都会举办大型的庆祝活动。今年的程序员节也不例外，每个班级的同学都发了橙子。

班级里有 $n$ 名同学从前到后排成一排，且已经得知了这些同学的成绩，其中第 $i$ 名同学的成绩是 $a_i$。班主任想根据同学们上个阶段的考试成绩来评定发橙子的数量。为了激励成绩优秀同学，发橙子时需要满足如下要求：

• 相邻同学中成绩好的同学的橙子必须更多。若相邻的同学成绩一样，则它们分到的数量必须平等。
• 每个同学至少分配一个橙子

由于预算有限，班主任希望在符合要求的情况下发出尽可能少的橙子。请问，至少需要准备多少橙子呢？

输入格式

第一行是一个整数 $n$，表示学生数量。

接下来一行有 $n$ 个整数，第 $i$ 个整数 $a_i$，表示第 $i$ 个同学的成绩。

输出格式

输出答案，也就是需要最少准备多少个橙子。

输入输出样例 #1

输入 #1

5
3 4 5 4 3

输出 #1

9

输入 #2

31
2 6 10 7 10 7 9 8 3 10 2 5 4 2 1 10 4 10 7 8 8 6 10 9 3 5 7 9 10 6 5

输出 #2

63

说明/提示

样例 1 解释

每位同学拿到的橙子的数量分别是 $1,2,3,2,1$，所以至少需要准备 $9$ 个。

数据规模与约定(10个测试点)

对于全部的测试点，保证 $1 \leq n \leq 10^6$，$0 \leq a_i \leq 10^9$。