题目描述

连小朋友都知道，Robin 喜欢吃苹果。

Robin 有 n 箱苹果。第一个箱子里有 $a_1$ 个苹果，第二箱有 $a_2$ 个，第 i 箱有 $a_i$个。Robin 是个吃货，他今天突发奇想，希望 n 箱苹果吃完之后数量上满足以下的规律：

(1) 第一，每个箱子都不能空。

(2) 第二，苹果数量应该是递增的。也就是说，第一个箱子的苹果数少于第二个箱子，第二箱的苹果少于第三箱。。。。。。以此类推。

(2) Robin 今天有些饱，所以想通过吃尽量少的苹果同时数量上满足以上两个要求。请你输出陈老师吃掉的最少的苹果数量。如果他无法完成心愿就输出 -1 。

输入格式

第一行，一个正整数 n，表示苹果的箱数；

第二行 n 个正整数，依次代表 $a_1$，$a_2$，$a_3$，...，$a_n$ 。

数据范围

对于 40% 的数据，1 <= n <= 100

对于 100% 的数据，1 <= n <= 1000，1 <= $a_i$ <= 3000

输出格式

一个整数，即题目要求的答案。

样例

3
15 40 22

19

3
1 3 1

-1

3
1 1234 3000

0