Voltar

uCoder | 1086 | Nível: 8 | Tempo Limite: 10

Popularidade no Facebook

Adaptado por Erich Rodrigues

Competição: USP - Seletiva para Maratona de Programação, 2013


Hoje em dia todos estão conectados, participam do Facebook, publicam suas fotos no Instagram, seus vídeos no Youtube, e assim por diante. Até mesmo sistemas como GPS hoje se baseiam em redes sociais, tornando tudo mais divertido (e talvez mais difícil de entender, mas isso é outra conversa). Ser popular no Facebook é quase uma necessidade. Uma pessoa com menos de 700, 800 amigos pode ser considerado quase como um pária nessa nova realidade.

Talvez por isso algumas pessoas costumam exagerar quando dizem o número de amigos que possuem. Considere uma comunidade com N pessoas, e para cada uma delas, considere que sabemos o número de amigos que cada pessoa diz ter na comunidade. Sua tarefa neste problema é determinar se de fato é possível que todos os membros da comunidade estejam falando a verdade. Lembre que uma pessoa não pode ser amiga de si mesma, e duas pessoas não podem ser amigas várias vezes.


Entrada

A entrada é composta por diversas instâncias e termina com final de arquivo (EOF).
A primeira linha de cada instância contém um inteiro N . A segunda linha possui N inteiros, ai, separados por um espaço em branco, correspondendo ao número de amigos que a pessoa i diz ter na comunidade.
A entrada deve ser lida da entrada padrão.


Saída

Para cada instância imprima, em uma única linha, possivel se é possível que todos os membros da comunidade estejam falando a verdade, ou impossivel caso contrário.
A saída deve ser escrita na saída padrão.

 

Restrições
• 1 ≤ N ≤ 10^5
• 0 ≤ ai ≤ 10^5


Exemplo de Entrada Exemplo de Saída

3
1 1 1
3
2 2 2

impossivel
possivel