题目背景

新年到了，你需要给排成一队的小朋友们分发糖果。为了让小朋友们不吵闹，分发糖果需要满足两个关键要求：一是每个小朋友拿到的糖果数量不能少于他的预期值；二是每个小朋友（除了第一个）拿到的糖果数量必须严格多于前一个小朋友。请你计算出满足所有要求的前提下，至少需要购买多少颗糖果。

题目描述

有 n 个小朋友排成一排，第 i 个小朋友有一个糖果预期值 ai（即希望拿到至少 ai 颗糖果）。分发糖果时需满足以下两个条件： 第 i 个小朋友最终拿到的糖果数量 ≥ ai； 对于任意 i > 1，第 i 个小朋友拿到的糖果数量 > 第 i-1 个小朋友拿到的糖果数量。 请计算满足上述所有条件时，需要购买的糖果总数的最小值。

输入格式

第一行输入一个整数 n（1 ≤ n ≤ 1e5），表示小朋友的数量； 第二行输入 n 个整数 a1, a2, ..., an（1 ≤ ai ≤ 1e9），依次表示每个小朋友的糖果预期值。

输出格式

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

样例

5
1 3 2 2 1

19

样例解释

我们需要为每个小朋友分配满足条件的最少糖果，具体分配方案如下： 第 1 个小朋友：预期值为 1，分配 1 颗（满足 ≥1）； 第 2 个小朋友：需 > 前一个（1）且 ≥ 3，分配 3 颗； 第 3 个小朋友：需 > 前一个（3）且 ≥ 2，分配 4 颗； 第 4 个小朋友：需 > 前一个（4）且 ≥ 2，分配 5 颗； 第 5 个小朋友：需 > 前一个（5）且 ≥ 1，分配 6 颗。 总糖果数 = 1 + 3 + 4 + 5 + 6 = 19，这是满足所有要求的最小值。