There are three pegs, labeled A, B, and C. Initially, there are $N$ disks on peg A, while pegs B and C are empty. A move consists of taking the top disk from one peg and placing it onto another peg. There are three types of disks, represented by 1, 2, and 3. Your goal is to have all type 1 disks end up on peg A, all type 2 disks on peg B, and all type 3 disks on peg C. Find the minimum total number of moves required to achieve this goal.

Input

The first line contains an integer $N$, the total number of disks. The second line contains $N$ integers, each being 1, 2, or 3. These $N$ numbers represent the types of the disks on the first peg in the initial state, in order from top to bottom.

Output

Output a single integer, the minimum number of moves.

Examples

Input 1

5
1 2 1 3 3

Output 1

8

Note

The initial state is shown below:

Initial state

The sequence of moves is as follows:

Move 1: Move disk 1 from peg A to peg C. Move 2: Move disk 2 from peg A to peg B. Move 3: Move disk 1 from peg A to peg B. Move 4: Move disk 1 from peg C to peg B. Move 5: Move disk 3 from peg A to peg C. Move 6: Move disk 3 from peg A to peg C. Move 7: Move disk 1 from peg B to peg A. Move 8: Move disk 1 from peg B to peg A.

Constraints

For 20% of the data, there are no more than 2 types of disks; For 40% of the data, $N \le 300$; For 100% of the data, $N \le 1000$.