Pawns

Time limit0.2sMemory limit64 MB

Summary

Pawns slide or jump toward their own side on a 1 by N board; find the minimum number of moves to gather all white pawns on the left and black on the right.

Level: Medium6 of 10
Topics: BFS, Simulation, Brute force
Solved: No attempts yet

Problem

"Pawns" is a game played on a board of length $N$ and width $1$ . The board is divided into $N$ unit squares, numbered $1, 2, \ldots, N$ from left to right. At any moment each square is either empty or occupied by a single pawn. Every pawn is either white or black. You are given the initial position of every pawn.

Pawns move according to the following rules:

A white pawn moves in one of two ways:
- it moves to the square immediately to its left, if that square is empty;
- it jumps two squares to the left if the square immediately to its left is occupied by another pawn and the square two to its left is empty (it jumps over its left neighbour).
A black pawn moves in one of two ways:
- it moves to the square immediately to its right, if that square is empty;
- it jumps two squares to the right if the square immediately to its right is occupied by another pawn and the square two to its right is empty (it jumps over its right neighbour).

A pawn must always remain on the board after moving. Note that whenever a pawn can move, exactly one of its two moves is possible, because the two conditions are mutually exclusive.

The game is complete when all white pawns occupy the front (leftmost) squares and all black pawns occupy the back (rightmost) squares, with no gaps: the white pawns fill positions $1, 2, \ldots$ contiguously, and the black pawns fill positions $N, N-1, \ldots$ contiguously.

Given the initial positions, find the minimum number of moves needed to complete the game. It is guaranteed that the game can be completed in a finite number of moves.

Input

The first line contains the integer $N$ , the length of the board. The second line contains $N$ integers from the set $\{0, 1, 2\}$ separated by single spaces: $0$ is an empty square, $1$ is a white pawn and $2$ is a black pawn. The $i$ -th number describes the $i$ -th square of the board.

Output

Output a single integer: the minimum number of moves needed to complete the game.

Constraints

$2 \le N \le 13$ ;
every test has at least one white pawn and at least one black pawn.

Hint

For the sample board 2 0 0 2 1, the initial configuration and the configuration after each of the $5$ moves are illustrated below:

Examples1

Example 1
Input
```
5
2 0 0 2 1
```
Expected output
```
5
```