问题描述

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

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

输入格式

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

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

输出格式

输出一个整数，表示最少操作次数使得数组所有数字变成 $1$。

样例输入

6  
1 3 5 2 7 1

样例输出

9

说明

$1 \leq n \leq 10^5$

$1 \leq a[i] \leq 10^5$