题目描述

$n$ 个学生站成一排，已知每名学生的考试成绩，老师要根据成绩按以下规则分发糖果：

• 每个学生至少得到一个糖果；

• 相邻两个学生中成绩高的会获得更多的糖果；

• 相邻两个学生成绩即使相同，获得的糖果数量也可以不同。

求：老师最少需要准备多少颗糖果?

例如：有3个学生，他们的考试成绩分别是70，50，80，可以给第一个学生2颗糖果，给第二个学生1颗糖果，给第三个学生2颗糖果，所以最少需要准备5颗糖果。

输入描述

第一行：一个正整数$n(1\le n \le 20000)$，表示学生人数。

第二行：$n$ 个整数$a_i(0 \le a_i \le 100)$，表示每个学生的考试成绩。

输出描述

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

样例

3
70 50 80

5

6
3 4 5 6 1 1

12