Caminho

A pista de treinos de corridas da Prefeitura tem formato circular, com $N$ postes igualmente espaça- dos na circunferência da pista, cada poste com exatamente uma lâmpada. Atualmente há lâmpadas de várias potências luminosas nos postes.

Vamos chamar o trecho de pista entre duas lâmpadas adjacentes (ou seja, uma vizinha à outra) de trecho escuro se a soma das potências luminosas dessas duas lâmpadas é menor do que $1\ 000$.

Para justificar um pedido à Prefeitura para que troquem as lâmpadas, os atletas querem saber qual o maior número de trechos escuros consecutivos (ou seja, um imediatamente em seguida de outro) da pista. Você pode ajudá-los?

Entrada

A primeira linha da entrada contém um inteiro $N$, o número de postes. Cada uma das $N$ linhas seguintes contém um inteiro $P_i$, a potência luminosa de uma lâmpada. A posição de cada lâmpada é dada pela ordem da entrada (ou seja, a ordem das lâmpadas ao longo da pista é a ordem dada na entrada).

Saída

Seu programa deve produzir uma única linha, contendo um único inteiro, o maior número de trechos escuros consecutivos.

Restrições

• $2 \leq N \leq 500\ 000$
• $1 \leq P_i \leq 1\ 000$ para $1 \leq i \leq N$

Informações sobre a pontuação

• Para um conjunto de casos de testes valendo $40$ pontos, $P_1 + P_N \geq 1\ 000$.

Exemplos

Exemplo de entrada 1

3
499
500
499

Exemplo de saída 1

3

Explicação do exemplo 1: O maior (e único) caminho de pares de lâmpadas com potência luminosa abaixo do especificado é formado pelos pares $(499,500)$, $(500, 499)$ e $(499, 499)$, portanto a resposta é $3$.

Exemplo de entrada 2

6
900
700
100
900
200
700

Exemplo de saída 2

1

Explicação do exemplo 2: O único par de lâmpadas com potência luminosa abaixo do especificado é $(700,100)$, portanto a resposta é $1$.

Exemplo de entrada 3

6
500
800
290
700
200
400

Exemplo de saída 3

4

Explicação do exemplo 3: O maior (e único caminho) com pares de lâmpadas com potência menor do que o especificado é formado pelos pares $(290,700)$, $(700,200)$, $(200,400)$ e $(400,500)$, portanto a resposta é $4$.

Exemplo de entrada 4

2
500
600

Exemplo de saída 4

0

Explicação do exemplo 4: Não há nenhum par de lâmpadas com potência abaixo do especificado, portanto a resposta é $0$.

Exemplo de entrada 5

2
100
101

Exemplo de saída 5

2

Explicação do exemplo 5: O maior (e único caminho) com pares de lâmpadas com potência menor do que o especificado é formado pelos pares $(100,101)$ e $(101,100)$, portanto a resposta é $2$.