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