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.