该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在神隐世界里，千寻（Chihiro）被委派去给一队神灵孩子分糖果。第 $i$ 位孩子至少想要 $a_{i}$ 颗糖果，并且他分到的糖果必须严格多于前一位孩子得到的糖果，否则会哭闹。千寻想尽量节省糖果，请你帮她计算出至少需要多少颗糖果，才能让所有孩子都开心。

Format

Input

第一行，一个正整数 n（孩子数量）。 第二行，n 个正整数 $a_{1}$ $a_{2}$ ... $a_{i}$（第 i 个孩子至少想要的糖果数）。

Output

输出一个整数，表示至少需要准备的糖果总数。

Samples

4
1 2 3 4

10

数据范围

1 ≤ n ≤ 1000

1 ≤ $a_{i}$ ≤ $10^{9}$

Limitation

1s, 1024KiB for each test case.