SPOJ Brasil

Mas que azar, o bairro onde você mora está sem internet por tempo indeterminado, e justo agora que uma banda local gravou um CD com músicas originais e você e seus amigos queriam escutar. Se houvesse internet, todos poderiam baixar as músicas online no mesmo dia, porém como não há vocês terão que se virar emprestando cópias do CD e gravando outras.

Mas que azar, o bairro onde você mora está sem internet por tempo indeterminado, e justo agora que uma banda local gravou um CD com músicas originais e você e seus amigos queriam escutar. Se houvesse internet, todos poderiam baixar as músicas online no mesmo dia, porém como não há vocês terão que se virar emprestando cópias do CD e gravando outras.

Inicialmente há uma cópia do CD. Há N pessoas no seu bairro, e cada uma tem um determinado estoque de CD's virgens para gravar novas cópias.

Digamos que uma pessoa receba a cópia do CD no tempo t. Ela começará imediatamente a produzir tantas cópias quanto possível, de acordo com seu estoque, e tais cópias estarão disponíveis nos tempos t+1, t+2, …, t+M, onde M é o número de CD's em estoque dessa pessoa.

Dado o número de CD's que cada pessoa tem em estoque em casa, encontre uma estratégia e diga qual o menor tempo necessário para que todos tenham em casa uma cópia do CD.

Entrada

Haverá diversos casos de teste. Cada caso de teste inicia com um inteiro N (1 ≤ N ≤ 10⁶), indicando o número de pessoas no bairro.

Em seguida haverá N inteiros Si (0 ≤ Si ≤ N), indicando o número de CD's que a i-ésima pessoa tem em estoque, para todo 1 ≤ i ≤ N.

O último caso de teste é indicado quando N = 0, o qual não deverá ser processado.

Saída

Para cada caso de teste imprima uma linha, contendo um inteiro, indicando o menor tempo necessário para que todas as pessoas do bairro tenham um cópia do CD em casa. Caso não seja possível que todas as pessoas tenham uma cópia do CD, imprima -1.

Exemplo

Entrada:
2 
0 1 
4 
1 1 0 1 
4 
0 2 1 2 
0

Saída:
2 
4 
3