Problem B
Police
Librarian Jurica has
-
moving the books one place to the left or to the right on a shelf if the place to the left or to the right is available,
-
taking a book from a shelf and placing it to an available place on that or any other shelf.
Careful Jurica can’t move books if he has a book in his hands. Additionally, he can’t take more than one book at once.
Jurica has been having back pains ever since he had to move all the volumes of the printed edition of Wikipedia from the first to the second floor so now he wants to put all the books in place with as little lifting as possible because his back is hurting. What is the minimal number of lifting he needs?
Input
The first line of input contains the integers
Each of the following
Number
In the initial and final state of the shelves, the same books will appear.
Output
The first and only line of output must contain the required
minimal number of lifting or
Sample Input 1 | Sample Output 1 |
---|---|
2 4 1 0 2 0 3 5 4 0 2 1 0 0 3 0 4 5 |
2 |
Sample Input 2 | Sample Output 2 |
---|---|
3 3 1 2 3 4 5 6 7 8 0 4 2 3 6 5 1 0 7 8 |
4 |
Sample Input 3 | Sample Output 3 |
---|---|
2 2 1 2 3 4 2 3 4 1 |
-1 |