Sort

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

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

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

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο $N(2\le N\le 100000)$.
Η δεύτερη γραμμή εισόδου περιέχει μια μετάθεση των πρώτων $N$ φυσικών αριθμών που πρέπει να ταξινομηθεί.

Έξοδος

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

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

input

2
2 1

output

1

input

4
4 3 2 1

output

1

input

4
3 1 4 2

output

3