题目描述

SHY和他的朋友们玩一种独特的扑克牌游戏，这个游戏使用一副有 $N$ 种不同牌面（$1 \leq N \leq 100,000$）的牌组，牌面被简单编号为 $1$ 到 $N$（普通的牌组有 $N = 13$）。在这个游戏中，只能打出一种牌型：可以选择一张标号为 $i$ 的牌和一张标号为 $j$ 的牌，并打出从 $i$ 到 $j$ 的所有牌。这种牌型称为「顺子」。

SHY的手牌中当前持有 $a_i$ 张牌面为 $i$ 的牌（$0 \leq a_i \leq 100000$）。帮助他找到必须打出的最少顺子数目以清空他所有的牌。

输入格式

第一行输入一个整数 $N$。

第二行到第 $1+N$ 行：第 $i+1$ 行包含 $a_i$ 的值。

输出格式

SHY必须打出的最少顺子数目以清空他所有的牌。

输入输出样例 #1

输入 #1

5 
2 
4 
1 
2 
3

输出 #1

6

说明/提示

【样例 1 解释】

SHY可以打出一个从 $1$ 到 $5$ 的顺子，一个从 $1$ 到 $2$ 的顺子，一个从 $4$ 到 $5$ 的顺子，两个从 $2$ 到 $2$ 的顺子，以及一个从 $5$ 到 $5$ 的顺子，总共需要 $6$ 轮来清空他所有的牌。

【数据范围】

对于所有测试数据有：$1 \le n \le 10^{5}, 0 \le a_i \le 10^5$。