题目描述

小红在玩战略游戏，地图上有n个国家排成一排，小红的军队初始时在1号国家，她需要率领军队进攻n号国家。

军队每从一个国家移动到一个相邻国家就需要消耗1单位的粮食，每个国家都会售卖粮食，每单位价格为ai，小红可以购买任意单位的粮食。

若军队携带的粮食数量大于1单位，小红需要对大于1的部分付出额外的代价运输粮食，每运输1单位粮食移动到一个相邻国家需要花费1。

小红想知道她要到达n号国家的最少花费是多少。

输入描述

第一行输入一个整数n表示国家个数。

第二行输入 n 个整数表示每个国家的粮食售价 。

1 <= n <= 1e5;

1 <= ai <= 1e5.

输出描述

输出一个整数表示答案。

输入示例

4
1 3 2 4

输出示例

5

提示信息

在第1个国家购买2单位粮食，花费2。

将1单位粮食从第1个国家运送到第2个国家，花费1。

在第2个国家购买0单位粮食，花费0。

在第3个国家购买1单位粮食，花费2。

因此答案为2+1+2=5。

时间限制：c/c++：1s；其他语言：3s。