Background

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

Description

现在，Robin有\(n\)箱苹果，第一个箱子里有\(n_1\)个苹果，第二个箱子里有\(n_2\)个，第\(i\)箱有\(n_i\)。

他今天突发奇想，希望\(n\)箱苹果吃完之后数量上满足以下规律:

1. 这些箱子都不为空
2. 每个箱子内苹果的数量递增，即\(n_1<n_2<...<n_i<n_{i-1}\)

Robin今天吃撑了，希望通过吃尽量少的苹果来满足以上两个要求。

现，请你输出Robin吃掉最少苹果的数量，如果他实在无法完成心愿就输出 -1 吧

Format

Input

第一行，一个正整数\(n\)，表示箱子的个数

第二行，\(n\)个正整数，以此表示\(a_1\)、\(a_2\)、\(a_3\)、...、\(a_n\)

Output

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

Sample 1

Input

3
15 40 22

Output

19

Sample 2

Input

3
1 3 1

Output

-1

Sample 3

Input

3
1 2 3

Output

0

Limitation&Appointment

对于\(40\%\)的数据，\(1\le n\le100\)

对于\(100\%\)的数据，\(1\le n\le1000\)，\(1\le a_i\le3000\)

共\(10\)个测试点，对于每一个测试点，时间限制为\(1000ms\)，空间限制为\(128MiB\)，分值为\(10\)分。