题目描述

Bessie 和她的朋友们正在玩一种独特的扑克牌游戏，这个游戏使用的扑克牌有 $N$ 种不同的数字牌面，数字面值在 $1$ 到 $N$ 的范围内。她们规定在游戏中只能出一种牌型：选择一张标号为 $i$ 的牌和一张标号为 $j$ 的牌，并打出手上从 $i$ 到 $j$ 的所有面值的牌各一张。这种牌型称为「顺子」。

Bessie 的手牌中当前持有 $a_i$ 张面值为 $i$ 的牌。请你帮助她找到清空她所有的牌需要打出的最少顺子数量。

输入格式

第 $1$ 行为一个整数 $N$。

接下来 $N$ 行，每行一个整数 $a_i$ 。

输出格式

输出一行一个整数，表示 Bessie 要0清空她所有的牌必须打出的最少顺子数目。

输入输出样例 #1

输入 #1

5 
2 
4 
1 
2 
3 

输出 #1

6 

Bessie 的手牌为： $2$ 张 $1$ ， $4$ 张 $2$ ， $1$ 张 $3$ ， $2$ 张 $4$ ， $3$ 张 $5$ ，她可以打出一个从 $1$ 到 $5$ 的顺子，一个从 $1$ 到 $2$ 的顺子，一个从 $4$ 到 $5$ 的顺子，两个从 $2$ 到 $2$ 的顺子，以及一个从 $5$ 到 $5$ 的顺子，总共需要 $6$ 轮来清空她所有的牌。

数据范围

对于 $100\%$ 的数据，有 $1 \leq N \leq 10^5 , 0 \le a_i \le 10^5$ 。

时限：1s

空间：256MB