发糖果的小考核

故事背景

期末考试结束后，老师准备给班里的同学分发糖果作为奖励。全班同学排成一排，每个人都有一个表现评分，分数越高代表表现越好。

老师制定了两个规则：

1. 每个同学至少要分到 1 颗糖果；
2. 相邻的两个同学中，评分更高的那位必须分到更多的糖果。

老师想知道，按照这两个规则，至少要准备多少颗糖果，才能完成这次发放任务。

题目描述

有 $n$ 位同学排成一排，从左到右第 $i$ 位同学的表现评分为 $a_i$。

你需要为每位同学分配糖果数量，使得：

• 每人至少分到 1 颗糖果；
• 如果某位同学的评分比他左边或右边相邻同学的评分高，那么他分到的糖果也必须严格更多。

在满足上述要求的前提下，求老师至少需要准备多少颗糖果。

输入格式

• 第一行包含一个整数 $n$，表示同学数量。
• 第二行包含 $n$ 个整数，表示从左到右每位同学的评分 $a_i$。

输出格式

• 输出一行，一个整数，表示所需糖果的最小总数。

输入输出样例 #1

输入 #1

5
1 0 2 2 3

输出 #1

8

样例解释 #1

一种最优分配方式是：糖果分配为 $[2, 1, 2, 1, 2]$，总共 8 颗糖果，满足所有规则。

说明/提示

• 对于所有测试数据，保证 $1 \le n \le 2 \times 10^5$。
• 评分为不超过 $10^9$ 的非负整数。
• 输出结果可能较大，请使用 64 位整数类型存储。