Knjige

Ο Mirko έχει μια οικιακή βιβλιοθήκη που αποτελείται από ~N~ βιβλία τοποθετημένα το ένα πάνω στο άλλο σε ένα στενό ντουλάπι. Επειδή ήταν καλά εκπαιδευμένος στα μυστικά του αλφαβήτου στην προηγούμενη εργασία, θέλει τώρα να τακτοποιήσει τα βιβλία αλφαβητικά, έτσι ώστε το βιβλίο του οποίου ο τίτλος έρχεται πρώτο αλφαβητικά να καταλήγει στην κορυφή και το αλφαβητικά τελευταίο στο κάτω μέρος του σωρού.

Ο Mirko μπορεί εύκολα να βγάλει ένα βιβλίο από το ντουλάπι, αλλά είναι δύσκολο να το σπρώξετε πίσω στο σωρό, επομένως το βιβλίο μπορεί να επιστραφεί μόνο στην κορυφή του σωρού. Έτσι, η μόνη διαθέσιμη μέθοδος ταξινόμησης των βιβλίων είναι να τραβήξετε επανειλημμένα ένα βιβλίο από το σωρό και να το τοποθετήσετε στην κορυφή του σωρού.
Τα βιβλία επισημαίνονται με ακέραιους αριθμούς από το ~1~ έως το ~N~, με αλφαβητική σειρά. Επομένως, ο Mirko θέλει να διατάσσονται ως ~(1,\;2,\;\ldots\;,\;N)~, μετρώντας από την κορυφή. Για παράδειγμα, εάν ~N = 3~ και η αρχική σειρά είναι ~(3,\;2,\;1)~, αρκούν δύο κινήσεις. Αρχικά, βγάζει το βιβλίο νούμερο ~2~ και το τοποθετεί από πάνω, οπότε ο σωρός γίνεται ~(2,\;3,\;1)~. Μετά από αυτό, κάνει το ίδιο με το βιβλίο νούμερο ~1~, οπότε ο σωρός γίνεται ~(1,\;2,\;3)~.
Βοηθήστε τον Mirko υπολογίζοντας τον ελάχιστο αριθμό κινήσεων που απαιτούνται για την ταξινόμηση μιας δοσμένης αρχικής σειράς.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~N\;(N \leq 300\,000)~.
Κάθε μία από τις επόμενες ~N~ γραμμές περιέχει έναν μόνο θετικό ακέραιο αριθμό. Αυτοί οι ~N~ ακέραιοι αριθμοί αντιπροσωπεύουν τη σειρά των βιβλίων του Mirko από πάνω προς τα κάτω του ντουλαπιού. Καθένας από τους ακέραιους ~1,\;2,\;\ldots\;,\;N~ εμφανίζεται ακριβώς μία φορά.

Έξοδος

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

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

input

3
3
2
1

output

2

input

4
1
3
4
2

output

2