题目背景

山谷里要架一条高架管道，管道靠一排立柱撑起来。立柱要落在规划好的位置上，但每个位置的地面高低不一：地面高的地方，立柱就得从更高的地方起。

题目描述

管道的走向上有 $n$ 个立柱位置，从左到右编号 $1$ 到 $n$。第 $i$ 个位置的地面高度为 $a_i$，立柱从地面立起，因此它顶端的架设高度 $h_i$ 不能低于 $a_i$，即 $h_i \ge a_i$。

架设规范限制：任意相邻两根立柱的顶端高度之差不能超过 $1$，也就是对所有 $1 \le i < n$ 都有 $|h_i - h_{i+1}| \le 1$。高度差更大时，两段管道之间的接头会因为弯折过剧烈而无法密封。

请你给出每根立柱的顶端高度，使得 $h_1 + h_2 + \cdots + h_n$ 最小。输出这个最小值。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

一行一个整数，表示立柱总高度的最小值。

输入输出样例 #1

输入 #1

3
3 1 3

输出 #1

8

输入输出样例 #2

输入 #2

3
1 5 1

输出 #2

13

输入输出样例 #3

输入 #3

4
1 1 1 1

输出 #3

4

说明

样例解释

样例 1 的最优方案是 $h = (3, 2, 3)$，总和为 $8$。第一根立柱不能低于 $3$；第二根比第一根最多低 $1$，比第三根也最多低 $1$，而第三根不能低于 $3$，所以 $h_2$ 至少是 $2$。

样例 2 的最优方案是 $h = (4, 5, 4)$，总和为 $13$。中间那根立柱不能低于 $5$，两侧的立柱各自与它相差不超过 $1$，所以两侧都至少是 $4$。

样例 3 中所有取值都是 $1$ 就已经合法，总和为 $4$。

数据范围

• 对于 $30\%$ 的数据，$1 \le n \le 2000$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le a_i \le 10^9$。