By Hamilton José Brumatto, UESC Brazil
The game, for two people, has a sequence with N even numbers and N odd values, N being itself an odd number. This sequence is arranged randomly. Each round a player chooses a number from one of the extremities. In the end, anyone with the most even numbers wins. For example, consider the following arrangement (with three odd and even pairs):
4 1 8 11 2 7
The first player wins getting all three even numbers for himself. On the other hand, for the following sequency:
5 8 4 7 6 3
The first player, considering that both play for the best success, will win with only 2 even numbers. Always wanting the best result, the inventor of the game asked you to make a program that already predicted with how many even numbers, the first player wins, considering that both play for the best success.
The input has several test cases, each test case occupy two lines, the first line has an odd number N, 0 < N < 500, in the second line, 2N integers, where N is even and N is odd, in any arrangement, each value is in the interval [0..10000]. The test cases end with N = 0.
For each entry case, on the output will be printed on a single line the number of even numbers that the first player will get if both players play for the best success.
|Input Sample||Output Sample|