题目描述

禾木面前有$n$堆牌，每堆数量不等。

禾木一次可以将第$i$堆到第$j$堆各打一张出去，求最少几次打完。

输入格式

输入包括两行。

第一行包含一个整数 $n$ ，代表牌堆的数量。

第二行包含$n$个整数，第$i$个整数$a_i$表示第$i$堆牌有$a_i$张牌。

输出格式

输出包括一行，包含$1$个整数，为打完所有牌最少需要的次数。

样例 #1

样例输入 #1

5 
2 4 1 2 3

样例输出 #1

6

样例 #2

样例输入 #2

5
3 1 4 1 5

样例输出 #2

10

说明/提示

【样例解释 #1】

打牌顺序为：

1. 区间$[1, 5]$的牌
2. 区间$[1, 2]$的牌
3. 区间$[4, 5]$的牌
4. 区间$[2, 2]$的牌
5. 区间$[5, 5]$的牌

共六次打牌。

【数据范围】

$1 \le n \le {10}^5$；

$1 \le a_i \le {10}^5$。