题目描述

一场隆重的巨人族婚礼正在进行。

喜庆的节日自然少不了发喜糖环节。

现在有 $n$ 个巨人站成一排等着发喜糖，每个巨人都有一个身高值（整数）。

身材高的巨人总是有优越感，所以发的喜糖不能比旁边矮的巨人少。

于是主人便定了以下规则发喜糖：

• 每个巨人至少能分到 $1$ 个糖果。
• 相邻两个巨人身高更高的会获得更多的果糖。

按以上规则给每个巨人发果糖，请统计下 最少的果糖数目 。

输入格式

输入有两行。

第一行有一个整数 $n$。

第二行有 $n$ 个整数 $h_i$，分别表示 $n$ 个巨人的身高。

输出格式

输出一个整数，表示最少得果糖数目。

样例

3
1 0 2

5

【样例 $1$ 解释】

分发 $2,1,2$ 颗

3
1 2 2

4

【样例 $2$ 解释】

分发 $1,2,1$ 颗

数据范围

对于 $10 \%$ 的数据，$1 \leq n \leq 100$ 且身高具有单调性（递增或者递减）；

对于 $40 \%$ 的数据，$1 \leq n \leq 10000$，$h_i \leq 10000$；

对于 $100 \%$ 的数据，$1 \leq n \leq 500000$，$h_i \leq 1000000$。