#31. 填空数列

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: _qhy_

题目描述

给定一个长为 的非负整数数列

对于 中的每个 ,你需要将其修改为任意的正整数,并满足修改后的整个数列严格上升

修改的方法可能不唯一,请你找出数列的和最小的一种修改方案,并输出这个和。如果找不到一种修改方案使得数列 严格上升,则输出

一个长为 的数列 严格上升,当且仅当对于所有的 ,都有

输入格式

第一行一个正整数 ,表示数列 的长度。

第二行 个非负整数,用一个空格隔开,表示给定的数列

输出格式

输出一行一个正整数 ,表示数列在修改后最小可能的和。

如果没有可行的修改方案,输出

样例

样例输入1

3
1 0 3

样例输出1

6

样例输入2

3
1 0 2

样例输出2

-1

数据范围与提示