Catacombs#82
The pirate catacombs on Treasure Island were dug as follows. From a hidden entrance, a cave opens, from which two tunnels depart—one to the left and one to the right. Each tunnel ends in a cave, from which two more tunnels depart, and so on. Each tunnel's length is one unit. Terminal caves, located at distance from the entrance, have no further exits. No tunnels cross or lead to the same cave. The number is called the depth of the catacombs.
In each terminal cave, there is a treasure chest. Before the arrival of Captain Jack Sparrow on the island, the pirates decided to relocate these chests according to the captain's latest instructions. The pirates drew a map of the catacombs and numbered the terminal caves from left to right. For each chest, they determined into which cave it should be moved before the captain arrives. After the rearrangement, each cave must again contain exactly one chest.
For the security of the treasures, pirates may swap two chests between any two caves. Each new swap starts only after the previous one is finished.
Your task is to compute the minimal total distance pirates must cover to place the chests in their required caves.
The first line contains a single integer (1 \le D \le 8) — the depth of the catacombs. The second line contains 2^D distinct integers from to 2^D. The -th number tells the final cave for the chest initially in cave .
Print a single integer — the minimal total distance pirates must carry the chests. Print a single integer — the number of swaps. Each of the next lines must contain two integers — the numbers of the caves being swapped. Output swaps in the order they should be performed.
Example 1
First, chests in caves and are swapped. The distance covered is (each chest moves units). Then, chests in caves and , and then and are swapped. Each swap covers distance . As a result, all chests arrive at their required caves and the total distance is .