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

🍬 分糖果问题

题目描述

有 n 位小朋友排成一队等待老师分糖果。第 i 位小朋友要求：

1. 至少得到 ai 颗糖果
2. 分得的糖果数量 必须比分给前一位小朋友的糖果数量更多（否则会不开心）
   老师想知道最少需要准备多少颗糖果才能让所有小朋友都开心。

输入格式

• 第一行：正整数 n（小朋友人数）
• 第二行：n 个正整数 a1, a2, ..., an（每位小朋友至少需要的糖果数）

输出格式

• 一行：一个整数（最少需要准备的糖果总数）

样例

样例1

输入

4  
1 4 3 3  

输出

16  

样例2

输入

15
314 15926 53589793 238462643 383279502 8 8 4 1 9 7 1 6 9 3

输出

4508143253

提示

对于所有测试点，保证 1 ≤ n ≤ 1000，1 ≤ ai ≤ 10^9