Anya is playing a game with ~N~ vertical line segments, numbered from ~1~ to ~N~.

Before Anya plays the game, you can draw as many line segments as you want, each connecting exactly ~2~ adjacent vertical lines. You can connect two lines more than once. However, lines must not overlap.

After you draw all the line segments, Anya traces ~N~ paths, each starting from the bottom of one of the ~N~ positions. The way Anya's trace works is as follows: she starts moving upward, and if she ever sees a segment connected with an adjacent line, she takes it, after which she continues upward. She continues until it reaches the top. Segments connecting vertical lines cannot share a point, so this path is unambiguous.

After reaching the top, Anya marks down the number she started at.

Anya really likes the array ~A~, and wants the top numbers to be equal to ~A~. Find the minimum number of connectors required to obtain the array ~A~, or determine that it is impossible.

Constraints

~1 \le N \le 3\,000~

~1 \le A_i \le N~

Input Specification

The first line contains the integer ~N~.

The next line contains ~N~ integers ~A_i~.

Output Specification

If it is impossible to obtain ~A~ and make Anya happy, output -1.

Otherwise, output the minimum number of line segments required to make Anya happy.

Scoring

For each test case:

If you correctly determine that there is a way to make Anya happy but output the wrong number of moves, you will receive ~30\%~ of the points. Specifically, if the correct answer is some non-negative integer ~J~, and you output a non-negative integer ~U~ less than ~2^{64}~ with ~J \ne U~, you will receive ~30\%~ of the points for that case.

Otherwise, you will receive ~100\%~ of the points if your output matches the judge's, and no points otherwise.

Sample Input 1

4
3 4 2 1

Sample Output 1

5

Explanation for Sample 1

An optimal configuration of lines is shown below.

The path Anya traces for the number ~1~ is shown below in red.

Sample Input 2

2
2 2

Sample Output 2

-1