Luna Likes Love

Η Luna είχε μια «ασυνήθιστη» ιδέα. Ευθυγράμμισε τους ~2n~ φίλους της σε μια μεγάλη γραμμή και έδωσε σε καθένα από αυτούς έναν ακέραιο αριθμό μεταξύ των ~1~ και ~n~, συμπεριλαμβανομένων και αυτών. Κάθε αριθμός χρησιμοποιείται ακριβώς δύο φορές. Κάθε ζευγάρι φίλων που μοιράζονται τον ίδιο αριθμό δημιουργούν ένα ζευγάρι.

Η Luna θέλει να στείλει καθένα από τα ~n~ ζευγάρια σε ραντεβού. Ωστόσο, δεν είναι τόσο απλό. Για να στείλετε ένα ζευγάρι σε ραντεβού, οι δύο φίλοι που δημιουργούν το ζευγάρι πρέπει να στέκονται ο ένας δίπλα στον άλλο, δηλαδή, δεν μπορεί να υπάρχει κανένας άλλος ανάμεσα τους.

Υπάρχουν δύο πιθανές ενέργειες που μπορεί να κάνει η Luna:

• Μπορεί να ανταλλάξει δύο φίλους που στέκονται ο ένας δίπλα στον άλλο, στη γραμμή.
• Εάν ένα ζευγάρι στέκεται ήδη ο ένας δίπλα στον άλλο στη γραμμή, η Λούνα μπορεί να τους στείλει σε ραντεβού. Αυτό αφαιρεί το ζευγάρι από τη γραμμή. Οι υπόλοιποι φίλοι μετατοπίζονται για να συμπληρώσουν το κενό που δημιουργήθηκε στη γραμμή.

Οι ενέργειες μπορούν να εκτελεστούν με οποιαδήποτε σειρά. Π.χ., μπορεί να κάνει κάποια ανταλλαγή, μετά να στείλει μερικά ζευγάρια φίλων σε ραντεβού και, στη συνέχεια, να επιστρέψει στις ανταλλαγές.

Βρείτε και αναφέρετε τον ελάχιστο αριθμό ενεργειών που απαιτούνται για την αποστολή όλων σε ραντεβού.

Eίσοδος

Η πρώτη γραμμή της εισόδου περιέχει έναν ακέραιο ~n~.

Η δεύτερη γραμμή της εισόδου περιέχει ~2n~ ακέραιους ~a_i (1 \le a_i \le n)~, χωρισμένους με ένα κενό διάστημα - η ακολουθία των αριθμών που έλαβαν οι φίλοι στη μεγάλη γραμμή, με τη σειρά.

Έξοδος

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

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~7~	Για κάθε ζευγάρι δεν υπάρχει άτομο μεταξύ των δύο φίλων που το σχηματίζουν και ~1 \le n \le 100~.
~2~	~8~	Για κάθε ζευγάρι υπάρχει το πολύ ένα άτομο μεταξύ των δύο φίλων που σχηματίζουν ένα ζευγάρι, και ~1 \le n \le 100~.
~3~	~11~	Οι πρώτοι ~n~ φίλοι στη γραμμή έλαβαν ακέραιους αριθμούς από το ~1~ έως το ~n~, ο καθένας ακριβώς μία φορά, όχι απαραίτητα στη σειρά. Επιπλέον, ~1 \le n \le 3\,000~.
~4~	~16~	Οι πρώτοι ~n~ φίλοι στη γραμμή έλαβαν ακέραιους αριθμούς από το ~1~ έως το ~n~, ο καθένας ακριβώς μία φορά, όχι απαραίτητα στη σειρά. Επιπλέον, ~1 \le n \le 500\,000~.
~5~	~22~	~1 \le n \le 3\,000~
~6~	~36~	~1 \le n \le 500\,000~

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

input

3
3 1 2 1 2 3

output

4

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

Στο πρώτο δείγμα, η Luna θα μπορούσε να ξεκινήσει ανταλλάσσοντας τον τρίτο και τον τέταρτο φίλο. Μετά από αυτήν την ανταλλαγή, η γραμμή φαίνεται ως εξής: ~3\,1\,1\,2\,2\,3~.

Στη συνέχεια, μπορεί να στείλει το ζευγάρι με τον αριθμό ~1~ και το ζευγάρι με τον αριθμό ~2~ σε ραντεβού (με οποιαδήποτε σειρά). Μόλις το κάνει, οι δύο φίλοι με τον νούμερο ~3~ βρίσκονται τώρα δίπλα-δίπλα και η Luna μπορεί να τους στείλει σε ραντεβού.

Συνολικά, αυτή η λύση λαμβάνει ~4~ ενέργειες: μία ανταλλαγή και τρία ραντεβού.

input

5
5 1 2 3 2 3 1 4 5 4

output

7