Copiado al portapapeles
Descripción
Una secuencia de números se denomina que \textit{sube y baja} si la diferencia de números sucesivos alterna entre números negativos y positivos. La primera diferencia si existe puede ser positiva o negativa.
Una secuencia con dos o menos números es la secuencia trivial.
Por ejemplo la secuencia ($1,7,4,9,2,5$) tiene la propiedad \textit{sube y baja} porque las diferencias ($6,-3,5,-7,3$) son alternadamente positivas y negativas. En contraste la secuencia ($1,4,7,2,5$) no es una secuencia \textit{sube y baja} porque la primera diferencia es positiva, La secuencia ($1,7,4,5,5$) tampoco es una secuencia \textit{sube y baja} porque la última diferencia es cero.
Dada una secuencia de enteros, devuelva la longitud máxima de la subsecuencia \textit{sube y baja} que se puede formar. Una subsecuencia se obtiene borrando algunos elementos (tal vez cero) de la secuencia original, dejando los elementos restantes en su orden original.
Entrada
La entrada consiste de varios casos de prueba. La primera línea de cada caso de prueba tiene el número ($0 \leq N \leq 50$ de elementos de la secuencia. La segunda línea de cada caso de prueba contiene los ($0 \leq N_i \leq 1000$) números de la secuencia separados por un espacio. La entrada termina cuando no hay más datos.
Salida
Para cada caso de prueba imprima en una línea la máxima subsecuencia que sube y baja que se pueda formar.
Ejemplo Entrada
6 1 7 4 9 2 5 10 1 17 5 10 13 15 10 5 16 8 1 44 9 1 2 3 4 5 6 7 8 9 19 70 55 13 2 99 2 80 80 80 80 100 19 7 5 5 5 1000 32 32 50 374 40 854 203 203 156 362 279 812 955 600 947 978 46 100 953 670 862 568 188 67 669 810 704 52 861 49 640 370 908 477 245 413 109 659 401 483 308 609 120 249 22 176 279 23 22 617 462 459 244
Ejemplo Salida
6 7 1 2 8 36