Catacombs
The Pirate's catacombs on the island of Treasures were tunneled on such principle. After the hidden entrance located a cave from which two tunnels go out – to the left and to the right. Each of tunnels ends with a cave from which two tunnels go out also, and etc. The length of each tunnel is equal to one. Eventual caves are in the distance D from an entrance. These caves do not have subsequent outputs. Tunnels between itself do not intersect, and does not conduce to one cave. The number D is named as depth of catacombs.
It is hidden one box with treasure in each of eventual caves. Pirates decided to move these boxes pursuant to the last pointing of Captain Jeck Sperrou before he will arrive on the island. Pirates drew the plan of catacombs and numbered eventual caves from left to right. Then for every treasure was the number of cave in which he must find oneself before Captain will arrive. In every cave again will find only one box after moving.
Pirates can only exchange between itselfs boxes from two caves to provide safety of treasures. It is possible to begin other only upon termination of one exchange. It is necessary to find the least total distance which pirates needed to carry boxes, that to place their in necessary rank.
Input
The first line contains the depth of catacombs D (D ≤ 8). The second line contains 2^D different integers from 1 to 2^D. Every i of them identifies the number of cave in which must to be situated the box, which is in a cave with number i at first.
Output
The first line contains the minimum total distance which will be passed by pirates with treasures. Second line contains an integer K - the proper quantity of exchanges. Each of the next K lines contains two numbers, the cave numbers between which the exchange takes place. The exchanges must be printed in the order they occur.