Get Minimum Increment

Choose any set of pairwise non-adjacent positions and add the same non-negative integer x to all of them, in this single operation only, so that the array becomes non-decreasing. Find the minimum x; output -1 if it is impossible. If the array is already non-decreasing, you may choose the empty set and take 0.

输入格式

The first line contains n, and the second line contains the array. On this site 1≤n≤200000, −10^9≤element≤10^9.

输出格式

Output one integer, the answer.

样例 1

输入：

4
1 1 3 2

输出：

1

样例 2

输入：

3
3 2 1

输出：

-1

样例 3

输入：

3
1 2 3

输出：

0

样例说明

The examples give 1, -1 and 0 respectively.