DMOPC '22 Contest 2 P2 - Line Trace

View as PDF

Submit solution

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

Problem type

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.


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.


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

3 4 2 1

Sample Output 1


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

Sample Output 2



There are no comments at the moment.