题目内容

你驾驶一辆能源车沿着一条直线依次经过 $n$ 个能源站，从第 $1$ 个站出发，目标是到达第 $n$ 个站。能源车每从一个站行驶到相邻的下一站需要消耗恰好 $1$ 单位能量。你可以在任意能源站购买任意数量的能量，第 $i$ 个站的单位能量价格为 $p_i$。由于能量存储不稳定，若当前携带超过 $1$ 单位能量，每多出 $1$ 单位能量并且行驶一站，就需要支付 $1$ 单位的维护费用。换句话说，如果在第 $j$ 个站购买了若干能量，将其中的 $1$ 单位能量用于从第 $i-1$ 个站到第 $i$ 个站的行驶（$i > j$），该单位能量的总花费等于 $p_j$ 加上沿途的维护费用 $i-j$。你希望合理规划在哪些站购买能量，使得总花费最小。请计算从起点到达终点所需的最小总花费。

能源站的数量 $n$ 满足 $1 \le n \le 10^5$，每个站的单价 $p_i$ 满足 $1 \le p_i \le 10^9$。

输入描述

第一行包含一个整数 $n$，表示能源站的数量。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，依次表示每个能源站的单位能量价格。