torturi

Adela lucrează la un laborator de cofetărie. Ea trebuie să pregătească două torturi de nuntă şi în acest scop va folosi $n$ blaturi de tort. Blaturile de tort au formă cilindrică, având toate aceeaşi înălţime, eventual diametre diferite. Blaturile ies pe rând din cuptor. Când un blat iese din cuptor, Adela îl va aşeza deasupra uneia dintre cele două stive de blaturi aflate pe cele două tăvi pe care se pregătesc torturile.

Blaturile diferă între ele prin rezistenţa la presiune. Rezistenţa unui blat creşte odată cu creşterea diametrului. Astfel, un blat va suporta deasupra sa oricâte alte blaturi cu diametre mai mici sau egale cu diametrul său. Pe de altă parte, dacă se aşează un blat de diametru $d$ deasupra altuia de diametru mai mic, atunci atât blatul aflat imediat dedesubt, cât şi toate blaturile din tort cu diametrul mai mic decât $d$ vor colapsa. Blatul de diametru $d$ se va stabiliza pe un blat cu diametru mai mare sau egal cu al său sau după caz, pe fundul tăvii.

Adela trebuie să folosească toate cele $n$ blaturi pentru pregătirea celor două torturi, şi să le aşeze pe cele două tăvi, în ordinea în care blaturile ies din cuptor. Dorinţa Adelei este ca numărul total de blaturi care nu vor colapsa în cele două torturi să fie maximă.

Cerinţă

Cunoscând diametrele blaturilor şi ordinea în care acestea ies din cuptor, să se determine numărul maxim de blaturi care nu vor colapsa.

Date de intrare

Fişierul de intrare torturi.in conține pe prima linie numărul natural $n$, reprezentând numărul de blaturi. Pe linia a doua se află $n$ valori naturale: $d_1, d_2, \dots, d_n$, nu neapărat distincte, separate prin câte un spațiu, reprezentând diametrele blaturilor de tort, în ordinea în care acestea ies din cuptor.

Date de ieșire

Fişierul de ieșire torturi.out conţine pe prima linie un număr natural care reprezintă numărul maxim de blaturi care nu vor colapsa în cele două torturi.

Restricţii şi precizări

• $2 \leq n \leq 250 \ 000$
• $1 \leq d_i \leq n$
• Un blat de tort nu poate fi aşezat în altă parte decât peste un alt blat așezat anterior sau direct pe una dintre cele două tăvi, dacă pe tavă nu s-a așezat încă un blat.

Exemplul 1

torturi.in

5
1 3 4 2 1

torturi.out

4

Explicaţie

Prima variantă de plasare optimă a blaturilor este: $3 \ 2$ pentru primul tort şi $4 \ 1$ pentru al doilea tort. Primul blat care iese din cuptor, de diametru $1$ va colapsa.
A doua variantă este: $3 \ 2 \ 1$ pentru primul tort şi $4$ pentru al doilea tort.

Exemplul 2

torturi.in

5
3 5 3 2 4

torturi.out

5

Explicaţie

Singura variantă de plasare optimă a blaturilor este: $3 \ 3 \ 2$ pentru primul tort şi $5 \ 4$ pentru al doilea tort. Niciun blat nu colapsează.