Παπούτσια

Ο Αντνάν είναι ιδιοκτήτης του μεγαλύτερου καταστήματος παπουτσιών στο Μπακού. Ένα κιβώτιο που περιέχει ~n~ ζεύγη παπουτσιών έχει μόλις φτάσει στο κατάστημα. Κάθε ζεύγος παπουτσιών έχει δύο παπούτσια του ίδιου μεγέθους: ένα αριστερό και ένα δεξί. Ο Αντνάν έχει τοποθετήσει και τα ~2n~ παπούτσια σε μία σειρά, η οποία αποτελείται από ~2n~ θέσεις αριθμημένες από το ~0~ μέχρι το ~2n - 1~, από τα αριστερά προς τα δεξιά.

Ο Αντνάν θέλει να αλλάξει τη σειρά των παπουτσιών σε μία έγκυρη διάταξη. Μία διάταξη είναι έγκυρη, αν και μόνο αν για κάθε ~i~ (~0 \le i \le n - 1~) ισχύουν οι ακόλουθες συνθήκες:

• Τα παπούτσια στις θέσεις ~2i~ και ~2i + 1~ έχουν το ίδιο μέγεθος.
• Το παπούτσι στη θέση ~2i~ είναι αριστερό παπούτσι.
• Το παπούτσι στη θέση ~2i + 1~ είναι δεξί παπούτσι.

Για να το πετύχει αυτό, ο Αντνάν μπορεί να κάνει μία σειρά αντιμεταθέσεων. Σε κάθε αντιμετάθεση, επιλέγει δύο παπούτσια που είναι γειτονικά εκείνη τη στιγμή και τα αντιμεταθέτει (δηλαδή τα σηκώνει και τοποθετεί κάθε ένα από αυτά στη θέση που βρισκόταν το άλλο). Δύο παπούτσια είναι γειτονικά, αν οι θέσεις τους διαφέρουν κατά ένα.

Να βρείτε το ελάχιστο πλήθος αντιμεταθέσεων που πρέπει να κάνει ο Αντνάν για να πετύχει μία έγκυρη διάταξη των παπουτσιών.

Λεπτομέρειες υλοποίησης

Να υλοποιήσετε την ακόλουθη συνάρτηση:

int64 count_swaps(int[] S)

• ~S~: ένας πίνακας αποτελούμενος από ~2n~ ακεραίους. Για κάθε ~i~ (~0 \le i \le 2n - 1~), το ~S[i]~ είναι μία μη-μηδενική τιμή που ισούται με το μέγεθος του παπουτσιού που τοποθετήθηκε αρχικά στη θέση ~i~. Εδώ, το |~x~| δηλώνει την απόλυτη τιμή του ~x~, που ισούται ~x~ με αν ~x \ge 0~ και ισούται με ~- x~ αν ~x < 0~. Αν ~S[i] < 0~, τότε το παπούτσι στη θέση ~i~ είναι αριστερό παπούτσι, αλλιώς είναι δεξί παπούτσι.
• Αυτή η συνάρτηση πρέπει να επιστρέφει το ελάχιστο πλήθος αντιμεταθέσεων (γειτονικών παπουτσιών) που πρέπει να γίνουν, ώστε να επιτευχθεί μία έγκυρη διάταξη.

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

Παράδειγμα 1

Έστω ότι έχουμε την ακόλουθη κλήση της συνάρτησης:

count_swaps([2, 1, -1, -2])

Ο Αντνάν μπορεί να πετύχει μια έγκυρη διάταξη με ~4~ αντιμεταθέσεις.

Για παράδειγμα, μπορεί πρώτα να αντιμεταθέσει τα παπούτσια ~1~ και ~-1~, μετά τα ~1~ και ~- 2~, ακολούθως τα ~- 1~ και ~- 2~ και, τέλος, τα ~2~ και ~- 2~. Πετυχαίνει λοιπόν την ακόλουθη έγκυρη διάταξη: [~- 2, 2, - 1, 1~]. Είναι αδύνατο να πετύχει μία έγκυρη διάταξη με λιγότερες από ~4~ αντιμεταθέσεις. Επομένως, η συνάρτηση πρέπει να επιστρέψει 4.

Παράδειγμα 2

Στο ακόλουθο παράδειγμα, όλα τα παπούτσια έχουν το ίδιο μέγεθος:

count_swaps([-2, 2, 2, -2, -2, 2])

Ο Αντνάν μπορεί να αντιμεταθέσει τα παπούτσια στις θέσεις ~2~ και ~3~ για να πετύχει την έγκυρη διάταξη [~- 2, 2, - 2, 2, - 2, 2~], επομένως η συνάρτηση πρέπει να επιστρέψει 1.

Περιορισμοί

• ~1 \le n 100\,000~
• Για κάθε ~i~ (~0 \le i \le 2n - 1~), ~1 \le S[i] \le n~.
• Είναι πάντα δυνατό να επιτευχθεί μία έγκυρη διάταξη των παπουτσιών με κάποιο αριθμό αντιμεταθέσεων.

Υποπροβλήματα

1. (~10~ βαθμοί) ~n = 1~
2. (~20~ βαθμοί) ~n \le 8~
3. (~20~ βαθμοί) Όλα τα παπούτσια έχουν το ίδιο μέγεθος.
4. (~15~ βαθμοί) Όλα τα παπούτσια στις θέσεις ~0, ..., n - 1~ είναι αριστερά παπούτσια και όλα τα παπούτσια στις θέσεις ~n, ..., 2n - 1~ είναι δεξιά παπούτσια. Επιπλέον, για κάθε ~i~ (~0 \le i \le n - 1~), τα παπούτσια στις θέσεις ~i~ και ~i + n~ έχουν το ίδιο μέγεθος.
5. (~20~ βαθμοί) ~n \le 1\,000~
6. (~15~ βαθμοί) Κανένας επιπλέον περιορισμός.

Υποδειγματικός βαθμολογητής

Ο υποδειγματικός βαθμολογητής διαβάζει την είσοδο ως εξής:

• γραμμή ~1~: ~n~
• γραμμή ~2~: ~S[0]~ ~S[1]~ ~S[2] ... S[2n - 1]~

Ο υποδειγματικός βαθμολογητής τυπώνει μία γραμμή που περιέχει την τιμή που επιστρέφει η συνάρτηση count_swaps.