Farmer John stellt $N$ Kühe für ein Foto auf ($1 \leq N \leq 50$). Die Höhe der $i$-ten ist $a(i)$. Eine lange nach Höhe steigende Teilfolge würde das Foto schön machen.

Eine Teilfolge besteht aus $a(i_1), a(i_2), \ldots, a(i_k)$ an Indizes $i_1 < i_2 < \ldots < i_k$. Sie heißt steigend, wenn $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$.

Für eine lange steigende Teilfolge darf er anfangs eine beliebige Teilfolge wählen und deren Elemente umkehren.

Zum Beispiel in der Liste

1 6 2 3 4 3 5 3 4

können die gewählten Elemente umgekehrt werden

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

und ergeben

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

Die umgekehrte Teilfolge benutzt dieselben Indizes; alle anderen Elemente bleiben unverändert.

Bestimme die maximale Länge einer steigenden Teilfolge, wenn eine beliebige Teilfolge einmal umgekehrt werden darf.

Eingabe

Lies von der Standardeingabe.

Die erste Zeile enthält $N$. Die übrigen $N$ enthalten $a(1) \ldots a(N)$, ganze Zahlen in $1 \ldots 50$.

Ausgabe

Schreibe auf die Standardausgabe.

Gib die Anzahl Elemente einer maximal langen steigenden Teilfolge nach Umkehrung höchstens einer Teilfolge aus.

Beispiele

Eingabe 1

9
1
2
3
9
5
6
8
7
4

Ausgabe 1

9

Aufgabenautor: Lewin Gan