Mila 喜欢玩俄罗斯方块。今天她学习了一种类似于俄罗斯方块的新游戏。这个新游戏有一个底部宽度为 $n$ 的无限长矩形场地，场地被划分为 $1 \times 1$ 的单元格。与真正的俄罗斯方块不同，在这个游戏中，使用的是高度为 $1$、宽度为 $x$（由 $x$ 个 $1 \times 1$ 单元格组成）的水平长条。在下一个方块下落之前，玩家可以选择其宽度 $x$ 为 $1$ 到 $n$ 之间的任意整数。方块不能旋转，但可以左右移动。方块会一直下落，直到碰到下方的已占用单元格或场地底部。
Mila 不喜欢在方块下方留下空单元格。她的目标是填充场地的下部行，使得所有已占用的单元格形成一个宽度为 $n$ 的矩形。
给定场地状态：$a_1, a_2, \dots, a_n$，其中 $a_i$ 表示场地第 $i$ 列中已占用单元格的数量。在给定的场地中，已占用单元格下方没有空单元格。例如，如果序列 $a$ 为 $3, 2, 4, 2, 2, 4$，场地看起来如下所示：
求 Mila 为了使已占用单元格形成一个宽度为 $n$ 的矩形，最少需要使用的方块数量。
输入格式
第一行包含一个整数 $n$ — 场地的宽度 ($1 \le n \le 2 \cdot 10^5$)。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ — 场地每一列中已占用单元格的数量 ($0 \le a_i \le 10^9$)。
至少有一个 $a_i$ 严格大于 $0$。
输出格式
输出一个整数：Mila 构建宽度为 $n$ 的矩形所需的最少方块数量。
子任务
| 子任务 | 分值 | $n$ | $a_i$ |
|---|---|---|---|
| 1 | 8 | $n \le 10$ | $a_i \le 5$ |
| 2 | 13 | $n \le 100$ | $a_i \le 500$ |
| 3 | 16 | $n \le 1000$ | $a_i \le 5000$ |
| 4 | 17 | $n \le 1000$ | $a_i \le 10^9$ |
| 5 | 25 | $n \le 10^5$ | $a_i \le 10^9$，当 $n > 1000$ 时序列 $a$ 随机生成 |
| 6 | 21 | $n \le 2 \cdot 10^5$ | $a_i \le 10^9$ |
样例
样例输入 1
6 3 2 4 2 2 4
样例输出 1
4
说明
在样例中，Mila 可以使用以下四个方块：