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 $A_i$, $1 \leq i \leq 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 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$, para $1 \leq i \leq N$

Informações sobre a pontuação

• Em um conjunto de casos de teste somando $40$ pontos, $N \leq 1\ 000$

Exemplos

Exemplo de entrada 1

10
20 5 10 5 15 15 15 5 6 22

Exemplo de saída 1

5

Exemplo de entrada 2

5
10 20 30 40 50

Exemplo de saída 2

2