XXVI Olimpíada Brasileira de Informática
Cortando o Papel
Uma folha de papel é composta de uma sequência de retângulos com diferentes alturas mas com larguras fixas, tal que as bases dos retângulos estão assentadas em uma linha horizontal. A figura ilustra uma folha exemplo com 33 retângulos. Nós gostaríamos de fazer um único corte horizontal, com a ajuda de um estilete e uma régua, que maximize o número resultante de pedaços separados pelo corte. A figura mostra quatro diferentes cortes que resultariam, respectivamente, em 4, 11, 10 e 3 pedaços.
Entrada
A primeira linha da entrada contém um inteiro N, representando o número de retângulos na folha de papel. A segunda linha contém N inteiros Ai, 1 ≤ i ≤ N, representando a sequência de alturas dos retângulos.Saída
Seu programa deve imprimir uma linha contendo um inteiro representando o número máximo de pedaços possível, com um único corte horizontal.Restrições
- 1 ≤ N ≤ 105
- 1 ≤ Ai ≤ 109, para 1 ≤ i ≤ N
Informações sobre a pontuação
- Em um conjunto de casos de teste somando 40 pontos, N ≤ 1000
Exemplos
Entrada
10 20 5 10 5 15 15 15 5 6 22 |
Saída
5 |
Entrada
5 10 20 30 40 50 |
Saída
2 |
