Sort

Εξετάστε τον ακόλουθο αλγόριθμο ταξινόμησης:

αντίστροφη ταξινόμηση (ακολουθία ~a~)
  όσο (το ~a~ δεν είναι σε μη φθίνουσα σειρά)
    χωρίστε το ~a~ στον ελάχιστο αριθμό κλίσεων
    για κάθε κλίση με μήκος μεγαλύτερο από ένα
      αντέστρεψε (κλίση)

Ως κλίση ορίζεται μια φθίνουσα διαδοχική υποακολουθία του ~a~. Η αντίστροφη διαδικασία θα αντιστρέψει τη σειρά των στοιχείων σε μια κλίση.
Σας δίνεται μια μετάθεση των πρώτων ~N~ φυσικών αριθμών των οποίων οι κλίσεις έχουν όλες ζυγό μήκος όταν χωρίζονται για πρώτη φορά. Προσδιορίστε τον συνολικό αριθμό των φορών που καλείται η αντίστροφη για την αντίστροφη ταξινόμηση της δεδομένης μετάθεσης.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο ~N\;(2 \leq N \leq 100\,000)~.
Η δεύτερη γραμμή εισόδου περιέχει μια μετάθεση των πρώτων ~N~ φυσικών αριθμών που πρέπει να ταξινομηθεί.

Έξοδος

Η μόνη γραμμή εξόδου πρέπει να περιέχει τον αριθμό των φορών που καλείται η αντίστροφη.

Παραδείγματα

input

2
2 1

output

1

input

4
4 3 2 1

output

1

input

4
3 1 4 2

output

3