背景

GESP三级(2506)

描述

有 $n$ 位⼩朋友排成⼀队等待⽼师分糖果。第 $i$ 位⼩朋友想要⾄少 $a_i$ 颗糖果，并且分给他的糖果数量必须⽐分给前⼀位⼩朋友的糖果数量更多，不然他就会不开⼼。

⽼师想知道⾄少需要准备多少颗糖果才能让所有⼩朋友都开⼼。你能帮帮⽼师吗？

格式

输入

第⼀⾏，⼀个正整数 $n$ ，表⽰⼩朋友的⼈数。 第⼆⾏， 个正整数 $a_1, a_2, ..., a_n$ ，依次表⽰每位⼩朋友⾄少需要的糖果数量。

输出

输出⼀⾏，⼀个整数，表⽰最少需要准备的糖果数量。

样例

4
1 4 3 3

16

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

4508143253

数据规模

对于所有测试点，保证 $1 \le n \le 1000, 0 \le a_i \le 10^9$。

限制

时间限制：1.0 s

空间限制：512.0 MB