Vladimir trabalhou por muitos anos fazendo matrioscas, aquelas bonecas aninhadas que representam o ofício russo. Uma matriosca é uma boneca que pode ser aberta, de modo que dentro dela se encontre uma outra boneca. Então, esta segunda boneca pode ser novamente aberta para se encontrar outra. Este processo pode ser repetido até que uma boneca final, que não pode ser aberta, seja encontrada.

Há algum tempo, ele teve a ideia de bonecas matrioscas generalizadas para brinquedos aninhados. Dessa forma, quando uma boneca é aberta, ela pode conter uma ou mais bonecas diretamente em seu interior. Esses novos brinquedos são chamados de matrioscas generalizadas.

Cada brinquedo corresponde a um número inteiro positivo. Quando abrimos um brinquedo do tipo $k$, encontramos brinquedos menores correspondentes a números $n_1, n_2, …, n_r$.

Se uma boneca do tipo $k$ puder ser aberta, então a soma das bonecas contidas diretamente nela deve ser exatamente $k - 1$, de forma que as menores se encaixem perfeitamente no interior. Se a soma fosse maior, então as bonecas menores não caberiam em $k$ e, se fosse menor, então a boneca $k$ estaria incompleta.

Já prevendo o sucesso de seu brinquedo, Vladimir gostaria de construir diversos conjuntos de bonecas, cada um vendido separadamente. Para simplificar a produção, cada conjunto será representado por uma sequência de inteiros de forma que a sequência para uma boneca do tipo $k$ começa com o número positivo $k$ e termina com o número negativo $-k$. Entre esses números, há uma ou mais sequências correspondentes às bonecas menores.

Você deve construir um programa matrioscas que verifique se uma dada sequência proposta por Vladimir representa de fato um conjunto de matrioscas generalizadas.

Entrada

A primeira linha da entrada contém o tipo da maior matriosca da sequência. A próxima linha contém uma sequência representando um conjunto de matrioscas generalizadas.

5
5 1 -1 3 1 -1 1 -1 -3 -5

Saída

Se a sequencia for válida, então o programa deve mostrar, para cada boneca presente na sequência, o número de bonecas contidas diretamente, conforme exemplo. As linhas devem estar ordenadas pelo tipo da boneca.

1 contem 0 bonecas
3 contem 2 bonecas
5 contem 2 bonecas

Pode ser que a sequência não seja válida. Isso acontece quando os números não estão aninhados corretamente, ou quando as bonecas menores não se encaixam perfeitamente. Nesse caso, a saída deve conter apenas uma mensagem sequencia invalida.

Dicas

Para ler uma sequência de inteiros até o final de arquivo, você pode consultar o resultado de scanf; leia a documentação. Por exemplo:

while (scanf("%d", ...) != EOF) {
    ...
}

Critérios

É obrigatório resolver o problema utilizando uma pilha.

Correção

Esta tarefa será corrigida automaticamente sempre que você realizar um git push. Depois de terminada a tarefa, deve-se utilizar o botão na interface de notas para solicitar a correção de um monitor.

← Anterior Voltar Próximo →