题目描述

n 个孩子站成一排。给你一个整数数组 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

1：每个孩子至少分配到 1 个糖果。

2：相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算需要准备的 最少糖果数目 。

输入格式

第一行是数组的长度 $N$ 。 第二行给出数组中的 $N$ 个整数 $a_i$ 。

输出格式

一个整数，你需要准备的最少的糖果数

样例输入

3
1 0 2

样例输出

5

样例分析

三个孩子的糖果数为 2 1 2

数据范围

对于 $100\%$ 的数据：$1 < N < 100000, 0 ≤ a_i ≤ 1000000000$ 。