XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: papel.x, onde x deve ser c, cpp, java, js ou py

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
	

 

Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação