B'Petya and his friend, the robot Petya++, went to BFDMONCON, where the costume contest is taking place today. While walking through the festival, they came across a scientific stand named after Professor Oak and Golfball, where they were asked to solve an interesting problem. Given a sequence of numbers a_1, a_2, ... , a_n you can perform several operations on this sequence. Each operation should look as follows. You choose some subsequence ^ dagger . Then you call all the numbers at odd positions in this subsequence northern, and all the numbers at even positions in this subsequence southern. In this case, only the position of the number in the subsequence is taken into account, not in the original sequence. For example, consider the sequence 1, 4, 2, 8, 5, 7, 3, 6, 9 and its subsequence (shown in bold) 1, mathbf{4}, mathbf{2}, 8, mathbf{5}, 7, 3, mathbf{6}, 9 . Then the numbers 4 and 5 are northern, and the numbers 2 and 6 are southern. After that, you can do one of the following: Thus, from the sequence 1, mathbf{4}, mathbf{2}, 8, mathbf{5}, 7, 3, mathbf{6}, 9 , if you choose the subsequence shown in bold, you can get either 1, mathbf{5}, mathbf{1}, 8, mathbf{6}, 7, 3, mathbf{5}, 9 or 1, mathbf{3}, mathbf{3}, 8, mathbf{4}, 7, 3, mathbf{7}, 9 . Then the operation ends. Note also that all operations are independent, i. e. the numbers are no longer called northern or southern when one operation ends. It is necessary to turn all the numbers of the sequence into zeros using the operations described above. Since there is very little time left before the costume contest, the friends want to know, what is the minimum number of operations required for this. The friends were unable to solve this problem, so can you help them? ^ dagger A sequence c is a subsequence of a sequence d if c can be obtained from d by the deletion of several (possibly, zero or al'...