Patrik
N ljudi stoji u redu čekajući ulaz na koncert. Kako je ljudima dosadno, stalno se osvrću i traže nekog poznatog u redu. Dvije osobe A i B koje stoje u redu mogu vidjeti jedna drugu ako su jedna pored druge ili ako između njih nema osobe koja je strogo viša od osobe A ili od osobe B. Napišite program koji određuje broj parova osoba koji se mogu vidjeti.
InputU prvom redu nalazi se prirodni broj N (1 ≤ N ≤ 500 000), broj osoba u redu. Svaki od sljedećih N redova sadrži po jedan prirodni broj, visinu jedne osobe u nanometrima. Sve osobe će biti niže od 2^{31} nanometara. Visine su dane u redoslijedu u kojem osobe stoje u redu.
OutputU prvi i jedini red ispišite broj parova osoba koje se mogu vidjeti.
Ulaz
Izlaz
7
2
4
1
2
2
5
1 Izlaz
10Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.