In their free time, Ayman and William really like to play Alternato! In Alternato, there is an array ~A~ with ~N~ positive integers. Ayman and William take turns, with Ayman going first. On each turn, a player can either choose any element and increment it by ~1~, or choose any element and decrement it by ~1~. During the process of this game, the integers may become ~0~ or negative.

As soon as the array becomes alternating (i.e. all elements are either strictly greater than their neighbors or strictly less than their neighbors), Ayman wins. However, if William can prevent that from happening within ~10^9~ moves, he wins.

Given the starting state of the array, determine how many moves it would take for Ayman to win, if possible!

Assume both players play optimally.

Constraints

~1 \leq A_i \leq 10^9~

Subtask 1 [40%]

~2 \leq N \leq 3000~

Subtask 2 [60%]

~2 \leq N \leq 2 \times 10^5~

Input Specification

The first line will contain an integer ~N~.

The second line will contain ~N~ space-separated integers, denoting the starting state of the array in Alternato.

Output Specification

If Ayman can win, output a single integer denoting the minimum number of moves he can win in. Otherwise, if William will win, print -1.

Sample Input

5
2 1 3 1 1

Sample Output

1

Explanation for Sample

If Ayman selects the last element and increments it by ~1~, he wins in ~1~ move.