Description

LL 最近在尝试各种各样的游戏。

某天 LL 在广告里看到了这样一个简单的游戏：有一个高度为 $n$ 层的塔，其中第 $1$ 到 $n$ 层分别有一个敌人，等级分别为 $a_1,\ldots,...,a_n$，玩家出生在第 $0$ 层，初始等级为 $1$，从低往高走，每到一层会与当层敌人决斗，如果玩家等级 $x$ 大于等于敌人的等级 $k$，那么将打败敌人，自己的等级将增加至 $x+k$，否则游戏失败。当玩家打败第 $n$ 层的敌人后，游戏通关。

此外，玩家随时可以选择付出一单位代价，等级增加一级，并返回到第 $0$ 层，复活所有被击败的敌人（敌人等级不变），因为这是一个很简单的游戏，所以 LL 不希望自己失败，并且希望在付出的代价尽可能少的情况下通关游戏，现在她想知道自己最少需要付出多少代价。

Input

第一行一个正整数 $n\ (1\le n\le 10^5)$，表示塔的高度。

接下来一行每行 $n$ 个正整数，分别表示 $a_1,a_2,\ldots,a_n\ (0\le a_i\le 10^9)$。

Output

输出一个整数表示 LL 所需要付出的最小代价。

Samples

6
2 0 5 9 22 30

3

Resources

The 21st UESTC Programming Contest Preliminary