One of our judges gets bored! Fortunately a toy named Hanoi Tower is there, which may help him to kill time. You know it well that the toy consists of three stacks and some disks. The size of each disk can be indicated by its radius and thickness. Tired of the usual ways of playing the toy, he devises his new rule. He uses only one stack in the game. Before the game, he colors one disk red, the others blue. Starting with an empty peg, the game runs on turn by turn. Each turn, he puts all the valid blue disks as well as the special red disk, which is not on the stack at the time, into a black box and picks out one blindly. By this way he can select one of the disks in the box with equal possibility. Which disk is so-called valid? It is decided by comparing its radius to the radius of the top-most disk on the stack. If its radius is strictly less than the top-most disk’s, it’s considered valid. If no disk is on the stack at that time, all the disks are considered valid. If a disk is chosen, our cute judge then puts it on the top of the stack, with one exceptional case, the red one. If the special red disk is chosen, instead of putting it onto the stack, the disk currently at the top of the stack should be removed. Wired, isn’t it?
The stack’s height is given. The game ends when after some turns the total thickness of all the disks on the stack is greater than the stack’s height, or the red disk is picked but the stack is empty. By then, the guy may get bored again and start to complain about his tedious work (doesn’t he suppose to be a judge?) Could you help us to figure out, after how many turns expectedly will the game last?