ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1054. Tower of Hanoi

Time limit: 1.0 second
Memory limit: 64 MB

Background

“Tower of Hanoi” puzzle is well known. There are 3 pegs with numbers: #1, #2 and #3. N disks of different diameters are set on the first peg in the following order: the lower disk is set, the larger diameter it has. Your aim is to move all disks onto the second peg using the third peg as an auxiliary one. Following the rules within a move it's allowed to replace only one uppermost disk. Besides it's forbidden to put the disk of the bigger diameter onto the disk of the smaller one.
Distribution of disks on the pegs during the game must be assigned as sequence D (Di is equal to the number of peg where the disk #i is placed on). For instance, sequence D = (3, 3, 1) means that the first and the second disks are set on the third peg and the third disk is on the first peg.
Example. Let's assume that three disks numbered in ascending order of diameters are set on the first peg. Then the movement of the disks can be depicted in the following table:
Step Peg #1 disks Peg #2 disks Peg #3 disks sequence D
0 1, 2, 3 - - 1, 1, 1
1 2, 3 1 - 2, 1, 1
2 3 1 2 2, 3, 1
3 3 - 1, 2 3, 3, 1
4 - 3 1, 2 3, 3, 2
5 1 3 2 1, 3, 2
6 1 2, 3 - 1, 2, 2
7 - 1, 2, 3 - 2, 2, 2

Problem

Your aim is to determine (using the given sequence D) the number of moves from the beginning of the game to the given position on condition of performing the optimal algorithm.
Optimal algorithm can be specified with the following recursive procedure.
procedure Hanoi(N, From, To_, Temp : integer);
begin
  if N > 0 then
  begin
    Hanoi(N - 1, From, Temp, To_);
    Writeln(N, From, To_);
    Hanoi(N - 1, Temp, To_, From)
  end
end;
For example, to move 5 disks it's enough to call Hanoi(5, 1, 2, 3).

Input

The first line contains an integer N that is the number of disks (1 ≤ N ≤ 31). The other N successive lines contain integers D1, …, DN (1 ≤ Di ≤ 3).

Output

Output the number of moves from the beginning of the game to the given position. If the given position cannot be achieved performing the optimal algorithm, output -1.
The answer will always be unequivocal, because positions are never repeated during the performing the optimal algorithm .

Samples

inputoutput
3
3
3
1
3
1
3
-1
Problem Source: Rybinsk State Avia Academy