Vuoristossa on rinnakkain $n$ huippua, joilla jokaisella on tietty korkeus. Lähdet matkaan riippuliitimellä valitsemaltasi huipulta.

Voit siirtyä huipulta $a$ huipulle $b$, jos huippu $b$ ja kaikki huiput $a$:n ja $b$:n välissä ovat matalampia kuin huippu $a$.

Monenko eri huipun kautta voit kulkea enintään reitilläsi?

Syöte

Ensimmäisellä rivillä on kokonaisluku $n$: huippujen määrä. Huiput on numeroitu $1,2,\dots,n$.

Seuraavalla rivillä on $n$ kokonaislukua $h_1,h_2,\dots,h_n$: huippujen korkeudet.

Tuloste

Tulosta yksi kokonaisluku: suurin mahdollinen huippujen määrä reitillä.

Esimerkki

Syöte:

10
20 15 17 35 25 40 12 19 13 12

Tuloste:

5

Osatehtävä 1 (18 pistettä)

• $1\le n \le 10$
• $1\le h_i \le 100$

Osatehtävä 2 (21 pistettä)

• $1\le n \le 5000$
• $1\le h_i \le 10^9$

Osatehtävä 3 (61 pistettä)

• $1\le n \le 2 \cdot 10^5$
• $1\le h_i \le 10^9$