Sequência da Onda
A Onda é uma sequência de inteiros. Ela tem algumas propriedades interessantes:
- A Onda tem tamanho ímpar, da forma ;
- Os primeiros inteiros da Onda formam uma sequência estritamente crescente;
- Os últimos inteiros da Onda formam uma sequência estritamente decrescente;
- Não há dois termos adjacentes iguais em uma Onda.
Por exemplo é uma sequência da Onda de comprimento 9. Entretanto 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:
.
Aqui, a maior Sequência da Onda é: . Logo, a saída será .
Entrada
O arquivo de entrada contem menos de casos de teste. A descrição de cada caso é dada abaixo. A entrada termina com fim de arquivo .
Cada caso começa com um inteiro positivo, . Nas próximas linhas, haverá 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 |