### 问题描述

一个数组 $a$ 中共包含 $n$ 个数，问最少多少次操作，可以让 $a$ 数组所有数都变成 $1$ 。

操作的内容是：每次操作可以任选一个区间使得区间内的所有数字减 $1$ 。 数据保证一定有解。

输入格式

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

第二行输入 $n$ 个整数表示数组 $a$ 。

输出格式

输出一个整数表示最少操作数可以让 $a$ 数组所有数字变成 $1$ 。

样例输入

6
1 3 5 2 7 1

样例输出

9

说明

保证对于所有数据有，$1 \leq n \leq 10^5,1 \leq a[i] \leq10^5$ 。