URI Online Judge | 2677

Par ou Ímpar

Por Hamilton José Brumatto, UESC BR Brazil

Timelimit: 1

O jogo, para duas pessoas, apresenta uma sequência com N valores pares e N valores ímpares, sendo N, em si, um número ímpar. Esta sequência está arranjada de forma aleatória. Cada rodada um jogador escolhe um número de uma das pontas. No final, quem ficar com mais números pares, ganha. Por exemplo, considere o seguinte arranjo (com três pares e três ímpares):

4 1 8 11 2 7

O primeiro jogador consegue vencer, obtendo todos os três valores pares para si. Mas se o arranjo fosse o seguinte:

5 8 4 7 6 3

O primeiro jogador, considerando que ambos joguem para obter o melhor êxito, irá vencer com apenas 2 valores pares. Querendo sempre o melhor resultado, o inventor do jogo pediu que você fizesse um programa que já previsse com quantos valores pares, o primeiro jogador vence, considerando que ambos joguem pelo melhor êxito.

Entrada

A entrada possui vários casos de teste, cada caso de teste ocupa 2 linhas, na primeira linha um valor N inteiro ímpar, 0 < N < 500, na segunda linha, 2N números inteiros, sendo N pares e N ímpares, em um arranjo qualquer, cada valor está no intervalo [0..10000]. Os casos de teste terminam com N = 0.

Saída

Para cada caso de entrada deve ser impresso em uma linha única o número de valores pares que o primeiro jogador irá ficar, se ambos jogadores jogarem para o melhor êxito.

Exemplo de Entrada Exemplo de Saída

3
4 1 8 11 2 7
3
5 8 4 7 6 3
1
1 2
0

3
2
1