401433: GYM100451 B Double Towers of Hanoi

This problem is a modification of the well-known "Tower of Hanoi" problem. There are three rods and 2n disks of n different sizes, two of each size. Let the disks be numbered by integers from 1 to 2n in non-decreasing order of size. Thus, the disks with numbers 2i - 1 and 2i have equal sizes. The disks can slide onto any rod. You can move only one disk from the top of any rod to the top of any other rod at a time. A larger disk can never be put over a smaller one.

Initially all the disks are on the first rod in the decreasing order of their numbers (counting from bottom to top). Finally they all should be posed to the second rod in a certain prescribed order. Your task is to find the minimal number of moves to get the final configuration from the initial one. Note that the disks with equal sizes but different numbers are considered to be different.

The first line contains the single integer n (1 ≤ n ≤ 2000). The second line describes the final order of the disks on the second rod. It contains 2n numbers in order from bottom to top. It is guaranteed that each of 2n disks appears in the given sequence exactly once. The final configuration is correct, i.e. there is no larger disk lying on a smaller one.

Output the required minimal number of moves.

1
2 1

3