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

噜噜发现了糖果宝库

1. 题目背景

小探险家噜噜和它聪明的小伙伴“一只羊”发现了一个古老的糖果宝库！宝库里有 $N$ 排糖果堆，但拿取这些糖果有一个奇特的规则。作为未来的编程高手，噜噜希望你能帮它计算一下，按照这个规则它最多能拿到多少糖果。

2. 问题描述

一共有 $N$ 堆糖果，从左到右依次编号为 $1, 2, \ldots, N$。第 $i$ 堆糖果有 $a_i$ 颗。 噜噜会从第一堆开始，依次决定从每一堆糖果中拿出多少颗。拿取规则如下：

1. 对于第一堆糖果 (编号为1)，噜噜会拿出 $a_1$ 颗糖果 (即，它会拿走第一堆中的全部糖果)。
2. 对于第 $i$ 堆糖果 (当 $i > 1$ 时)，设噜噜从前面 $i-1$ 堆（即编号为 $1$ 到 $i-1$ 的所有堆）中总共拿出的糖果数量之和为 $S_{i-1}$。噜噜从第 $i$ 堆可以拿出的糖果数量 $t_i$ 必须满足以下两个条件：
   • $t_i \le a_i$ (不能超过当前堆本身拥有的糖果数)。
   • $t_i \le S_{i-1}$ (不能超过前面所有堆已拿出糖果的总和)。
   • 如果 $S_{i-1} = 0$ (即前面没有拿出任何糖果)，则 $t_i$ 必须为 $0$。

噜噜总是想在规则允许的范围内，从当前考虑的堆中拿出尽可能多的糖果。请你计算，按照这个规则，噜噜最终能拿到的糖果总数。

3. 输入格式

第一行一个整数 $N$，表示糖果的堆数。 第二行 $N$ 个整数 $a_1, a_2, \ldots, a_N$，用空格隔开，表示每堆糖果的数量。

4. 输出格式

一个整数，表示噜噜按照规则最多能拿出的糖果总数。

5. 样例输入与输出

样例输入 1:

4
10 3 7 2

样例输出 1:

22

样例解释 1:

• 第1堆 ($a_1=10$): 噜噜拿出 $a_1 = 10$ 颗。
  • 已拿出糖果总和 $S_1 = 10$。 最终收集到的总糖果数 = 10。
• 第2堆 ($a_2=3$): 前面已拿出糖果总和 $S_1 = 10$。
  • 噜噜可拿出 $\min(a_2, S_1) = \min(3, 10) = 3$ 颗。
  • 已拿出糖果总和 $S_2 = S_1 + 3 = 10 + 3 = 13$。 最终收集到的总糖果数 = 10 + 3 = 13。
• 第3堆 ($a_3=7$): 前面已拿出糖果总和 $S_2 = 13$。
  • 噜噜可拿出 $\min(a_3, S_2) = \min(7, 13) = 7$ 颗。
  • 已拿出糖果总和 $S_3 = S_2 + 7 = 13 + 7 = 20$。 最终收集到的总糖果数 = 13 + 7 = 20。
• 第4堆 ($a_4=2$): 前面已拿出糖果总和 $S_3 = 20$。
  • 噜噜可拿出 $\min(a_4, S_3) = \min(2, 20) = 2$ 颗。
  • 已拿出糖果总和 $S_4 = S_3 + 2 = 20 + 2 = 22$。 最终收集到的总糖果数 = 20 + 2 = 22。

最终，噜噜最多能拿出 22 颗糖果。

样例输入 2:

5
5 12 3 20 8

样例输出 2:

34

样例解释 2：

• 第 1 堆（$a\_1=5$）：取走 5，累计 $S\_1=5$，总共取走 5。
• 第 2 堆（$a\_2=12$）：受限于 $S\_1=5$，取走 $\min(12,5)=5$，累计 $S\_2=5+5=10$，总共取走 $5+5=10$。
• 第 3 堆（$a\_3=3$）：受限于 $S\_2=10$，取走 $\min(3,10)=3$，累计 $S\_3=10+3=13$，总共取走 $10+3=13$。
• 第 4 堆（$a\_4=20$）：受限于 $S\_3=13$，取走 $\min(20,13)=13$，累计 $S\_4=13+13=26$，总共取走 $13+13=26$。
• 第 5 堆（$a\_5=8$）：受限于 $S\_4=26$，取走 $\min(8,26)=8$，累计 $S\_5=26+8=34$，总共取走 $26+8=34$。

6. 数据规模与约定

对于所有测试数据，满足 $1 \le N \le 10^5$，$0 \le a_i \le 10^9$。