Farmer John alinea $N$ vacas para una foto ($1 \leq N \leq 50$). La altura de la $i$-ésima es $a(i)$. Una subsecuencia creciente larga por altura le parece estética.

Una subsecuencia contiene elementos $a(i_1), a(i_2), \ldots, a(i_k)$ en índices $i_1 < i_2 < \ldots < i_k$. Es creciente si $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$.

Para obtener una subsecuencia creciente larga, puede elegir inicialmente cualquiera e invertir sus elementos.

Por ejemplo, en la lista

1 6 2 3 4 3 5 3 4

podemos invertir los elementos elegidos

1 6 2 3 4 3 5 3 4
  ^         ^ ^ ^

para obtener

1 4 2 3 4 3 3 5 6
  ^         ^ ^ ^

La subsecuencia invertida ocupa los mismos índices y los otros elementos no cambian.

Encuentra la longitud máxima de una subsecuencia creciente si puedes invertir una subsecuencia arbitraria una vez.

Entrada

Lee la entrada estándar.

La primera línea contiene $N$. Las restantes $N$ contienen $a(1) \ldots a(N)$, enteros en $1 \ldots 50$.

Salida

Escribe en la salida estándar.

Imprime el número de elementos de la mayor subsecuencia creciente posible tras invertir como máximo una subsecuencia.

Ejemplos

Entrada 1

9
1
2
3
9
5
6
8
7
4

Salida 1

9

Autor del problema: Lewin Gan