题目描述

坤坤有无穷多个篮球和篮子，他们存放在仓库里，于是坤坤想玩一个游戏。最初，坤坤面前只有一个篮子，篮子里面没有篮球。每一轮，坤坤可以对每个篮子做一次操作，一次操作是指以下 $3$ 种操作中的一种（假设这个篮子原本有 $x$ 个篮球）：

1. 从仓库里取一个篮球放进去，这样这个篮子里的篮球数量就变成了 $x+1$。
2. 从仓库里拿一个篮子，再从当前篮子拿 $y$ 个篮球到这个新篮子里去，即两个篮子的篮球分别变为 $x-y$ 和 $y$ 个（$0 \le y \le x$）。注意：这个新来的篮子只有到下一轮才能操作。
3. 什么都不做。

注意，每一轮只能对同一个篮子操作一次，每个篮子可以选择不同的操作，新拿来的篮子当前轮不能操作。

坤坤已经玩了很久了，但她并不知道自己玩了多少轮。已知现在有 $n$ 个篮子，篮子里篮球的数量分别为 $a_1, a_2, \dots, a_n$，请问坤坤最少玩了多少轮？

输入格式

从标准输入读入数据。

第一行，一个整数 $n$（$1 \le n \le 10^6$）。

第二行，分别表示 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^6$）。

输出格式

输出到标准输出。

输出一个整数，表示坤坤最少需要玩的轮数。

样例1输入

1
0

样例1输出

0

样例2输入

4
1 1 1 1

样例2输出

3

样例3输入

5
0 3 0 3 0

样例3输出

5

样例3解释

步骤为 $(0) \rightarrow (0,0) \rightarrow (0,0,0,0) \rightarrow (0,1,0,1,0) \rightarrow (0,2,0,2,0) \rightarrow (0,3,0,3,0)$ 一共 $5$ 轮。