Avançado Informática - Semana 20

Sequência da Onda

A Onda é uma sequência de inteiros. Ela tem algumas propriedades interessantes:

  • A Onda tem tamanho ímpar, da forma L = 2\cdot n+1;
  • Os primeiros (n+1) inteiros da Onda formam uma sequência estritamente crescente;
  • Os últimos (n+1) inteiros da Onda formam uma sequência estritamente decrescente;
  • Não há dois termos adjacentes iguais em uma Onda.

Por exemplo 1, 2, 3, 4, 5, 4, 3, 2, 0 é uma sequência da Onda de comprimento 9. Entretanto 1, 2, 3, 4, 5, 4, 3, 2, 2 não é uma sequência da Onda válida. Neste problema, você receberá uma sequência de inteiros. Você deve encontrar o comprimento da maior Sequência da Onda que é uma subsequência da sequência dada. Considere que a sequência dada seja:

1 \ 2 \ 3 \ 2 \ 1 \ 2 \ 3 \ 4 \ 3 \ 2 \ 1 \ 5 \ 4 \ 1 \ 2 \ 3 \ 2 \ 2 \ 1.

Aqui, a maior Sequência da Onda é: 1 \ 2 \ 3 \ 4 \ 5 \ 4 \ 3 \ 2 \ 1. Logo, a saída será 9.

Entrada

O arquivo de entrada contem menos de 75 casos de teste. A descrição de cada caso é dada abaixo. A entrada termina com fim de arquivo (EOF).

Cada caso começa com um inteiro positivo, N \ (1 \leq N \leq 10000). Nas próximas linhas, haverá N inteiros.

Saída

Para cada caso de teste, imprima o comprimento da maior Sequência da Onda.

Exemplo de Entrada Exemplo de Saída
10

1 2 3 4 5 4 3 2 1 10

19

1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1

5

1 2 3 4 5

9

9

1