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