Farmer John allinea $N$ mucche per una foto ($1 \leq N \leq 50$). L’altezza della $i$-esima è $a(i)$. Una lunga sottosequenza crescente per altezza renderebbe la foto bella.

Una sottosequenza contiene $a(i_1), a(i_2), \ldots, a(i_k)$ agli indici $i_1 < i_2 < \ldots < i_k$. È crescente se $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$.

Per una lunga sottosequenza crescente può inizialmente sceglierne una qualsiasi e invertirne gli elementi.

Ad esempio, nella lista

1 6 2 3 4 3 5 3 4

possiamo invertire gli elementi scelti

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

per ottenere

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

La sottosequenza invertita occupa gli stessi indici, lasciando gli altri elementi invariati.

Trovate la massima lunghezza di una sottosequenza crescente potendo invertirne una arbitraria una volta.

Input

Leggete dall’ingresso standard.

La prima riga contiene $N$. Le altre $N$ contengono $a(1) \ldots a(N)$, interi in $1 \ldots 50$.

Output

Scrivete sull’uscita standard.

Stampate il numero di elementi della massima sottosequenza crescente possibile dopo aver invertito al più una sottosequenza.

Esempi

Input 1

9
1
2
3
9
5
6
8
7
4

Output 1

9

Autore del problema: Lewin Gan