Dabelea Ioana Viviana (ioanavivianadabelea) Mario a primit de ziua lui un nou joc video, “ Up “. În acest joc are n baloane numerotate de la 1 la n. Fiecare balon i ( 1 ≤ i ≤ n ) se află la o distanță di de sol. La începutul jocului Mario poate alege oricare dintre cele n baloane pe care să se poziționeze. Aflându-se la un moment dat pe un balon cu numărul de ordine l, băiatul poare sări pe oricare alt balon cu indicele t doar daca l < t și dl < dt. Jocul continuă până când nu mai există baloane care să respecte condiția dată. Numărul de baloane pe care jucatorul sare este egal cu scorul obținut.
Cerința
Mario, curios din fire, vrea să afle care este scorul maxim pe care l-ar putea obține în joc.
Date de intrare
Fișierul de intrare up.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.
Date de ieșire
Fișierul de ieșire up.out va conține un număr natural k care reprezintă scorul maxim obținut la joc.
Restricții și precizări
1 ≤ n ≤ 100.000- numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât
1.000.000
Exemplu:
up.in
10 10 2 7 5 4 6 7 1 8 9
up.out
6
Explicație
O posibilitate de a obține scorul maxim este de a sări pe următoarele baloane: 2 4 6 7 9 10