SPOJ Brasil

Os habitantes de uma pequena ilha caribenha na região conhecida como Triângulo das Bermudas adoram gastar suas noites quentes de verão jogando cartas. Como um tributo para a região onde moram, todos seus jogos de cartas têm alguma conexão com triângulos. Um dos jogos mais populares na ilha é conhecido como Trincas, e tem regras bem simples.

O jogo é jogado entre dois amigos, com um baralho de cartas padrão. As cartas são distingüidas apenas por seus valores, de 1 (Ás) a 13 (Rei). As cartas são embaralhadas e colocadas em uma pilha no centro da mesa, viradas para baixo. Essa pilha é chamada de pilha. Os dois jogadores jogam em turnos. A cada turno, um jogador

• saca a carta do topo da pilha, adicionando ela para sua mão; e

• decide se ele/ela quer “baixar algumas trincas”.

Baixar uma trinca consiste de escolher três cartas (uma trinca) da mão e colocar elas na mesa, viradas para cima. Os trios baixados permanecem na mesa até o fim do jogo. Somente algumas combinações de cartas formam uma trinca válida. Existem dois tipos de trincas válidas:

• Trincas perfeitas são compostas de três cartas cujos valores representam os lados de um triângulo equilátero;

• Trincas comuns são compostas de três cartas cujos valores representam os lados de um triângulo não equilátero.

A figura abaixo mostra exemplos de trincas perfeitas (a), trincas comuns (b), e trincas inválidas (c).

Somente trincas válidas podem ser baixadas, mas um jogador pode baixar um número qualquer de trincas em um dado turno. Em particular, já que os jogadores sabem o número de cartas na pilha a cada turno, um jogador pode decidir baixar todas as trincas em seu último turno. Alguns jogadores, no entanto, normalmente baixam algumas trincas durante o jogo, para manter o mínimo de cartas possíveis em suas mãos.

O jogo acaba quando a pilha está vazia. O vencedor é o jogador que baixou o maior número de trincas perfeitas. Se os dois jogadores baixaram o mesmo número de trincas perfeitas, o vencedor é o jogador que baixou o maior número de trincas comuns. Se os dois jogadores baixaram o mesmo número de trincas perfeitas e o mesmo número de trincas comuns, o resultado é um empate.

Dada a descrição de cartas na pilha, escreva um programa que determina o vencedor de um jogo de Trincas, considerando que os dois jogadores jogam da melhor maneira possível.

Entrada

A entrada contém vários casos de teste. A primeira linha contém um inteiro N representando o número de cartas na pilha (6 <= N <= 10^4). A próxima linha contém N inteiros Xi, separados por espaço, representando as cartas na pilha (1 <= Xi <= 13, para 1 <= i <= N). As cartas são dadas na ordem que são sacadas pelos jogadores: a primeira carta da entrada (X1) é a primeira carta sacada, a segunda carta da entrada (X2) é a segunda carta sacada, e assim por diante. Várias cartas com o mesmo valor podem estar presentes na pilha, e não necessariamente todos os valores de cartas estão presentes na pilha. O final da entrada é dado por N = 0.

Saída

Para cada caso de teste seu programa devem imprimir uma única linha, contendo '1' se o primeiro jogador ganhar, '2' se o segundo jogador ganhar, ou '0' se tiver um empate.

Exemplo

Entrada
7
5 6 5 6 5 6 8
12
13 13 13 13 13 13 1 3 2 9 3 9
12
1 2 1 2 1 2 3 1 4 2 5 3
0

Saída
0
2
1