Kuglice

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

Αγόρασαν ~n~ χριστουγεννιάτικα στολίδια τοποθετημένα το ένα δίπλα στο άλλο σε ένα μακρόστενο κουτί, όπου το ~i~-οστό στολίδι έχει χρώμα ~a_{i}~. Το κουτί είναι ανοιχτό και από τις δύο πλευρές, οπότε τα στολίδια μπορούν να βγουν τόσο από την αριστερή όσο και από τη δεξιά πλευρά του κουτιού. Το κουτί είναι διαφανές, οπότε ο Marin και ο Josip να μπορούν να δουν το χρώμα κάθε στολιδιού.

Η εικόνα δείχνει την αρχική κατάσταση του κουτιού στο δεύτερο παράδειγμα.
Στην πρώτη του κίνηση, ο Marin μπορεί να πάρει είτε ένα στολίδι χρώματος ~1~ από το αριστερό άκρο του κουτιού είτε ένα στολίδι χρώματος ~3~ από το δεξί άκρο του κουτιού.

Ο Josip σκέφτηκε ένα παιχνίδι που θα έκανε το στόλισμα του δέντρου ακόμα πιο διασκεδαστικό, που είναι ήδη πολύ διασκεδαστικό από μόνο του. Το παιχνίδι έχει ως εξής: Ο Marin και ο Josip εναλλάσσουν σειρές και ο Marin ξεκινάει το παιχνίδι. Ο παίκτης στη σειρά του παίρνει ένα στολίδι από το κουτί (είτε από το αριστερό είτε από το δεξί άκρο του κουτιού) και το τοποθετεί στο δέντρο. Αν πάρει ένα στολίδι του οποίου το χρώμα δεν έχει παρθεί προηγουμένως, ο παίκτης κερδίζει ένα πόντο. Το παιχνίδι τελειώνει όταν παρθεί και το τελευταίο στολίδι από το κουτί.

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

Είσοδος

Η πρώτη γραμμή θα περιέχει έναν ακέραιο αριθμό ~n\;(1 \le n \le 3000)~, τον αριθμό των στολιδιών στο κουτί.

Η δεύτερη γραμμή θα περιέχει ~n~ ακέραιους αριθμούς ~a_{i}\;(1 \le a_{i} \le n)~, τα χρώματα των στολιδιών στο κουτί.

Έξοδος

Στην πρώτη και μοναδική γραμμή, εκτυπώστε το αποτέλεσμα του παιχνιδιού, δηλαδή δύο αριθμούς που συνδέονται με τον χαρακτήρα " ~:~ " (χωρίς εισαγωγικά), τα σκορ του Marin και του Josip.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~17~	~a_{i} \le 2~ για κάθε ~i = 1, ..., n~
~2~	~10~	~n \le 20~
~3~	~26~	~a_{i} \le 2~ για κάθε ~i = 1, ..., n~
~4~	~15~	~n \le 300~
~5~	~42~	Κανένας επιπλέον περιορισμός

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

input

5
1 1 2 1 1

output

1:1

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

Ο Marin είναι πρώτος και παίρνει ένα στολίδι χρώματος ~1~ από το αριστερό άκρο. του κουτιού. Ο Marin κερδίζει έναν πόντο.

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

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

Ο Josip παίρνει ένα στολίδι χρώματος ~2~ από το αριστερό άκρο του κουτιού. Αυτή είναι η πρώτη μπάλα χρώματος ~2~ που πάρθηκε, οπότε ο Josip κερδίζει έναν πόντο.

Ο Marin παίρνει το τελευταίο στολίδι (χρώμα ~1~) από το αριστερό άκρο του κουτιού, αλλά δεν κερδίζει πόντο και το παιχνίδι τελειώνει.

Ο Marin έχει συνολικά ~1~ πόντο (πήρε πρώτος το στολίδι του χρώματος ~1~), και Ο Josip έχει επίσης συνολικά ~1~ πόντο (πήρε πρώτος το στολίδι του χρώματος ~2~).

Το τελικό αποτέλεσμα είναι 1 : 1.

input

6
1 2 3 1 2 3

output

2:1