Exercise Deadlines

Ο Bob έχει ~N~ προγραμματιστικές ασκήσεις που πρέπει να ολοκληρώσει πριν από τις προθεσμίες τους. Η άσκηση ~i~ παίρνει μόνο μια μονάδα χρόνου για να ολοκληρωθεί, αλλά έχει μια προθεσμία ~d_i~ (~1~ ~\le~ ~d_i~ ~\le~ ~N~) μονάδες χρόνου από τώρα.

Ο Bob θα λύσει τις ασκήσεις σε μια σειρά που περιγράφεται από μια ακολουθία ~a_1~, ~a_2~, ..., ~a_N~, έτσι ώστε η ~a_1~ να είναι η πρώτη άσκηση που θα λύσει, ~a_2~ να είναι η δεύτερη άσκηση που θα λύσει, και ούτω καθεξής. Το αρχικό σχέδιο του Bob περιγράφεται από την ακολουθία ~1~, ~2~, ..., ~N~. Με μια πράξη ανταλλαγής, ο Bob μπορεί να ανταλλάξει δύο γειτονικούς αριθμούς σε αυτή την ακολουθία. Ποιός είναι ο ελάχιστος αριθμός ανταλλαγών που απαιτείται για να αλλάξει αυτή η ακολουθία σε μία που ολοκληρώνει όλες τις ασκήσεις έγκαιρα;

Είσοδος

Η πρώτη γραμμή αποτελείται από έναν μοναδικό ακέραιο ~N~ (~1~ ~\le~ ~N~ ~\le~ ~200\,000~). Η επόμενη γραμμή περιέχει ~N~ ακέραιους χωρισμένους με κενό ~d_1~, ~d_2~, ..., ~d_N~ (~1~ ~\le~ ~d_i~ ~\le~ ~N~).

Βαθμολογία

Για ~17~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~5\,000~.

Έξοδος

Εκτυπώστε έναν μόνο ακέραιο, τον ελάχιστο αριθμό ανταλλαγών που απαιτείται για να λύσει ο Bob όλες τις ασκήσεις έγκαιρα ή -~1~ αν αυτό είναι αδύνατο.

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

input

4
4 4 3 2

output

3

Επεξήγηση του 1ου παραδείγματος

Μία έγκυρη ακολουθία είναι η (~1~, ~4~, ~3~, ~2~), η οποία μπορεί να προκύψει από την (~1~, ~2~, ~3~, ~4~), με τρεις ανταλλαγές.

input

3
1 1 3

output

-1

Επεξήγηση του 2ου παραδείγματος

Υπάρχουν δύο ασκήσεις με που πρέπει να ολοκληρωθούν σε χρόνο ~1~, αλλά μόνο μια άσκηση μπορεί να λυθεί μέχρι εκέινη την ώρα.