Petriukas turi kortų kaladę, kurią sudaro n kortelių. Kiekvienoje kortelėje yra sveikas skaičius nuo 1 iki 100 000 imtinai. Ant kortelių esantys skaičiai gali kartotis.
Petriukas nusprendė surūšiuoti korteles. Norėdamas tai padaryti, jis paima viršutinę kortą iš kaladės ir, jei joje esantis skaičius yra lygus mažiausiam skaičiui tarp visų šios kaladės kortelių, tuomet jis padeda šią kortą į šoną. Priešingu atveju, jis padeda ją į kaladės apačią ir paima kitą viršutinę kortą. Procesas baigiasi, kai kaladėje nebelieka kortų. Petriukas daug kartų žaidė su šiomis kortomis, tad visada žino, koks yra mažiausias skaičius likusioje kaladėje.
Padėkite nustatyti, kiek kartų Petriukui reikės paimti viršutinę kortą.
Input
Pirmoje eilutėje sveikas skaičius n (1 \le n \le 10^5).
Antroje eilutėje n sveikų skaičių a_i (1 \le a_i \le 10^5).
Output
Išveskite atsakymą.
Examples
| standard input | standard output |
|---|
| 4
6 3 1 2
| 7
|
| 1
6
| 1
|
| 3
2 2 2
| 3
|