SPOJ Brasil

Árvores são estruturas de fundamental importância em diversas áreas como teoria dos grafos e otimização combinatória, e podem ser empregadas para modelar soluções de muitos problemas do mundo real. Em algumas situações, é desejável obter uma representação compacta para a topologia de uma árvore, com o objetivo de reduzir o esforço computacional para processá-la.

Uma das representações comumente utilizadas é a sequência de Prüfer. Dada uma árvore rotulada com n vértices, a sequência de Prüfer que a representa univocamente tem tamanho n-2 e pode ser gerada de maneira muito simples por meio de um algoritmo iterativo, que remove vértices da árvore até que restem apenas dois vértices. Mais especificamente, considere uma árvore T com n vértices, com rótulos {1,2,...,n}. Na i-ésima iteração do algoritmo (1 ≤ i ≤ n-2), considere que v_i denota o vértice folha com o menor rótulo em T. Atribua ao i-ésimo elemento da sequência de Prüfer o rótulo do único vértice adjacente a v_i e remova v_i de T. Ao final do algoritmo, a sequência de Prüfer terá tamanho n-2 e representará de maneira única a árvore rotulada T.

A sua tarefa é bem simples: determinar o grau de cada vértice da árvore representada por uma sequência de Prüfer.

Entrada

Há vários casos de teste.

Cada caso de teste é descrito em uma única linha, contendo inteiros separados por espaços em branco. O primeiro inteiro é o valor de K (1 ≤ K ≤ 1.048.576), que descreve o tamanho da sequência de Prüfer. Em seguida existem K inteiros s_i (1 ≤ s_i ≤ K + 2, \quad 1 ≤ i ≤ K), que descrevem a sequência de Prüfer.

A entrada termina com K=0, que não deve ser processado.

Saída

Para cada caso de teste, imprima uma única linha contendo uma sequência de K+2 inteiros g_i, em que g_i indica o grau do vértice de rótulo i da árvore representada pela sequência de Prüfer.

Exemplos

Entrada:
4 4 4 4 5
0

Saída:
1 1 1 4 2 1