uCoder | 1292 | Nível: 5 | Tempo Limite: 10
Isósceles
Adaptado por Erich Rodrigues
Competição: SBC - ACM/ICPC - Maratona de Programação de 2016
Os irmãos Sérgio e Luiz estavam brincando com cubinhos de madeira e queriam construir um muro, que acabou ficando incompleto, com as colunas tendo diferentes alturas, como nessa figura.
Eles decidiram agora que a brincadeira seria retirar cubinhos, sempre de cima para baixo nas colunas, de maneira que no final restasse apenas um triângulo isósceles de cubinhos. Eles podem apenas retirar cubinhos do muro, sem recolocar em outra coluna, e os triângulos têm que ser completos. A figura abaixo ilustra os cinco primeiros triângulos isósceles de cubinhos, do tipo que eles querem, com alturas 1, 2, 3, 4 e 5 respectivamente.
Dada a sequência de alturas das colunas do muro, seu programa deve ajudar Sérgio e Luiz a descobrir qual é a altura máxima que o triângulo poderia ter ao final. No muro da primeira figura, com 30 colunas de cubinhos, o triângulo mais alto possível teria altura igual a sete.
Entrada
A primeira linha da entrada contém um inteiro N , 1 ≤ N ≤ 50000, representando o número de colunas do muro. A segunda linha contém N inteiros Ai , 1 ≤ Ai ≤ N , para 1 ≤ i ≤ N , indicando as alturas de cada coluna.
Saída
Seu programa deve produzir uma única linha com um inteiro H, representando a altura máxima que um triângulo poderia ter ao final.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
8 |
1 |
|
16 |
6 |