Hanoi Tower with Operation Priority Strategy

The classical Tower of Hanoi puzzle consists of three pegs (labeled A, B, and C) and n disks of distinct sizes. Initially, all n disks are stacked on peg A in decreasing size from bottom to top. A legal move consists of taking the top disk from one peg and placing it on top of another peg, with the restriction that a disk can only be placed on an empty peg or on top of a larger disk.

Each move is denoted by two letters; for example, AB means moving the top disk from peg A to peg B. Before any moves are made, a unique priority is assigned to each of the six possible moves among the pegs: AB, AC, BA, BC, CA, and CB. At every step, among all legal moves the following strategy is used:

• (1) Choose the legal move with the highest priority (i.e. with the maximum priority value).
• (2) The disk being moved in the chosen move must not be the same disk that was moved in the immediately preceding move.

This process is repeated until all n disks have been moved from peg A onto one of the other pegs (either B or C). It can be proven that this strategy always leads to a solution.

Your task is to simulate the above process and compute the number of moves required.

Formally, let n be the number of disks. The game terminates when either peg B or peg C contains exactly n disks (in the correct order). At each step, denote the legal move by a two-letter code (e.g. AB) which has an assigned priority. Let the six operations have priorities given by $$P(AB),\;P(AC),\;P(BA),\;P(BC),\;P(CA),\;P(CB).$$ The move chosen is the legal move with the maximum priority and whose disk is different from the disk moved in the previous operation.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10), the number of disks.

The second line contains six distinct integers representing the priorities for the operations in the order: AB AC BA BC CA CB. A higher integer means a higher priority.

outputFormat

Output a single integer, the number of moves performed using the strategy until the puzzle is solved.

sample

1
6 5 4 3 2 1

1