Gaston is an employee of a famous comic magazine. One of his tasks (the one he dislikes most) is archiving mail. He archives infrequently, so a large part of his desk is taken up by an enormous pile of unprocessed letters. Sometimes, one of the editors needs a particular letter and Gaston is faced with the problem of finding that letter in the pile. Gaston realizes that he has a retrieval problem. Using sticks and threads, he has designed a system for better retrieving unarchived letters. In the middle of a stick, he attaches a letter. At both ends of the stick, a thread is attached where another stick (with letter and threads) can be fastened. He arranges the letters such that all letters under the left thread of a stick are alphabetically before the letter in the middle and the letters under the right thread are alphabetically after the letter in the middle. As this is true for every stick, this system creates a sorted tree, in which it is easy to find letters. When making a prototype, Gaston found out that he has a balancing problem. If there is a difference in weight between the ends of a stick, the stick is unbalanced, and the whole system collapses in an even bigger mess than before. Using some extra thread, Gaston invented an asymmetric fix in which a stick is still balanced if the left side contains one more letter than the right side. If the right side contains more letters, the stick is always unbalanced, so the fix is indeed asymmetric. Opinions about Gaston differ. He believes that he is a genius, but others are not so certain. The editors point out that when a letter is added, there is a fair chance that the tree gets out of balance and must be rearranged. We want you to find out how often the tree (or a subtree) must be rearranged, given a tree and a sequence of incoming letters. We have simplified the problem a bit. All letters have the same weight. Every letter has a unique (positive) number. The letters must be arranged according to their number. A stick is balanced if the left side contains the same number of letters as the right side or at most one more. A letter is added according to the following procedure: if its number is lower than the number of the letter on the stick, it is added to the left thread. If its number is higher, it is added to the right thread.
2/3 Following this procedure repeatedly, eventually a free thread is found. The letter is then attached to a fresh stick (having a free thread on both ends) which is tied to the free thread. Then, starting at the top, working downwards, the balance of all sticks are checked. If a stick is unbalanced, a balancing step is executed. Because a balancing step might cause other sticks to become unbalanced, the whole tree is checked again from top to bottom for unbalanced sticks. This is repeated until no unbalanced sticks are found. A balancing step is defined as bringing one unbalanced stick s into balance by removing a letter from the heavy side of the stick and adding one to the light side. This is done according to the following procedure:
3/3 Note: The picture on the right illustrates the first sample input below. Sample Input 2 3200500 4 1679 400 250 0 0 0 2 511 100 Sample Output 3 0