题目背景

Y 同学作为幼儿园的老师，正在组织一场分糖果的游戏。为了公平起见，也为了鼓励表现更好的小朋友，他制定了一套简单而又巧妙的规则。现在，他需要计算出最少需要准备多少颗糖果，才能让每个小朋友都满意。

题目描述

有 $N$ 个小朋友站成一排，从左到右编号为 $1$ 到 $N$。你得到了一个整数数组 ratings，其中 ratings[i] 是第 $i$ 个小朋友的评分。

你需要按照以下要求，给这些小朋友分发糖果：

1. 每个小朋友至少分配到 1 颗糖果。
2. 对于任意相邻的两个小朋友，评分更高的那个必须获得比他旁边小朋友更多的糖果。

请你计算，为了满足上述所有条件，至少需要准备多少颗糖果。

输入格式

第一行包含一个整数 $N$。 第二行包含 $N$ 个用空格隔开的整数 ratings[1], ratings[2], ..., ratings[N]。

输出格式

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

样例

样例输入 #1

3
1 0 2

样例输出 #1

5

样例输入 #2

3
1 2 2

样例输出 #2

4

提示

样例解释

• 样例 1: 评分序列为 [1, 0, 2]。

  • 一种最优的分发方案是 [2, 1, 2] 颗糖果。
  • 小朋友 1 (评分1) > 小朋友 2 (评分0)，所以糖果数 $2 > 1$。
  • 小朋友 3 (评分2) > 小朋友 2 (评分0)，所以糖果数 $2 > 1$。
  • 所有小朋友都至少有 1 颗糖果。
  • 总共需要 $2 + 1 + 2 = 5$ 颗糖果。

• 样例 2: 评分序列为 [1, 2, 2]。

  • 一种最优的分发方案是 [1, 2, 1] 颗糖果。
  • 小朋友 2 (评分2) > 小朋友 1 (评分1)，所以糖果数 $2 > 1$。
  • 小朋友 2 (评分2) = 小朋友 3 (评分2)，他们之间的糖果数量没有硬性要求，只需满足各自至少有 1 颗即可。
  • 总共需要 $1 + 2 + 1 = 4$ 颗糖果。

数据范围与约定

• $N$ 是 ratings 数组的长度。
• $1 \le N \le 2 \cdot 10^4$
• $0 \le \text{ratings}[i] \le 2 \cdot 10^4$