DMOPC '22 Contest 2 P2 - Line Trace

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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

Before Anya plays the game, you can draw as many line segments as you want, each connecting exactly 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 paths, each starting from the bottom of one of the 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 , and wants the top numbers to be equal to . Find the minimum number of connectors required to obtain the array , or determine that it is impossible.

Input Specification

The first line contains the integer .

The next line contains integers .

Output Specification

If it is impossible to obtain 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 of the points. Specifically, if the correct answer is some non-negative integer , and you output a non-negative integer less than with , you will receive of the points for that case.

Otherwise, you will receive 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 is shown below in red.

Sample Input 2

2
2 2

Sample Output 2

-1