Inversione di una sequenza#10555

Inversione di una sequenza

1 secondo

128 megabyte

Molto difficile

Il fattore John dispone le sue $n$ mucche in fila per fotografarle. L'altezza della $i$ -esima mucca in questa fila è $a_{i}$ a_i, e il fattore John pensa che la foto risulterebbe più esteticamente gradevole se nella fila ci fosse una lunga sottosequenza crescente di mucche per altezza.

Ricordiamo che una sottosequenza è una sequenza di elementi $a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{k}}$ a_{i_1}, a_{i_2}, \ldots, a_{i_k} della sequenza originale, i cui indici corrispondenti soddisfano la condizione $i_{1} < i_{2} < \dots < i_{k}$ i_1 < i_2 < \ldots < i_k. Chiamiamo una sottosequenza crescente se $a_{i_{1}} \leq a_{i_{2}} \leq \dots \leq a_{i_{k}}$ a_{i_1} \le a_{i_2} \le \ldots \le a_{i_k}.

Il fattore John vuole che la sua fila abbia una lunga sottosequenza crescente. Per ottenere ciò, può scegliere una qualsiasi sottosequenza di mucche e invertire l'ordine dei suoi elementi.

Ad esempio, supponiamo che le mucche siano disposte nel modo seguente:

1 6 2 3 4 3 5 3 4

Possiamo scegliere gli elementi contrassegnati qui sotto:

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

e invertirne l'ordine, ottenendo:

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

Si noti che gli elementi invertiti occupano esattamente lo stesso insieme di posizioni di prima dell'operazione, mentre tutti gli altri elementi rimangono invariati.

Determinare la massima lunghezza possibile di una sottosequenza crescente dopo che gli elementi di al più una sottosequenza sono stati riordinati in ordine inverso.

Input

La prima riga contiene il numero $n (1 \leq n \leq 50)$ n~(1 \le n \le 50). Nelle successive $n$ righe sono contenuti $a_{1}, \dots, a_{n}$ a_1, \ldots, a_n, dove ogni $a_{i}$ a_i è un numero intero compreso nell'intervallo $1 \dots 50$ .

Output

Stampare la massima lunghezza possibile di una sottosequenza crescente dopo aver invertito l'ordine degli elementi di al più una sottosequenza.

Esempi

Esempio 1