Patrik

~N~ άτομα περιμένουν στην ουρά για να μπουν σε μια συναυλία. Οι άνθρωποι βαριούνται να περιμένουν κι έτσι γυρίζουν και ψάχνουν κάποιο γνωστό στη γραμμή.

Δύο άτομα ~A~ και ~B~ που στέκονται στην ουρά μπορούν να δουν ο ένας τον άλλον εάν στέκονται ακριβώς δίπλα ο ένας στον άλλον ή εάν κανένα άτομο μεταξύ τους δεν είναι αυστηρά ψηλότερο από το άτομο ~A~ ή το άτομο ~B~.

Γράψτε ένα πρόγραμμα που να καθορίζει τον αριθμό των ζευγών ατόμων που μπορούν να δουν ο ένας τον άλλον.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει έναν ακέραιο αριθμό ~N~ ~(1 \le N \le 500\,000)~, τον αριθμό των ατόμων που στέκονται στην ουρά.

Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει έναν μόνο ακέραιο, το ύψος ενός ατόμου σε νανόμετρα. Όλοι θα είναι κοντύτεροι από ~2^{31}~ νανόμετρα.

Τα ύψη δίνονται με τη σειρά με την οποία στέκονται οι άνθρωποι στην ουρά.

Έξοδος

Τυπώστε τον αριθμό των ζευγών ατόμων που μπορούν να δουν ο ένας τον άλλο σε μία ουρά.

Παράδειγμα

input

7
2
4
1
2
2
5
1

output

10