Παιχνίδι συγχώνευσης 2

Το παιχνίδι συγχώνευσης που είχε δημιουργήσει ο Τάκης στην περσινή Β' Φάση προσέλκυσε πολύ κόσμο στην πιτσαρία του, αλλά αποδείχθηκε ιδιαίτερα δύσκολο για τους νεαρούς επισκέπτες του. Έτσι, ο Τάκης αποφάσισε να δημιουργήσει ένα ευκολότερο παιχνίδι. (Σημείωση: Δε χρειάζεται να διαβάσετε ή να λύσετε το περσινό θέμα για να λύσετε αυτό, είναι ανεξάρτητα μεταξύ τους.)

Στον παίκτη δίνεται ένας πίνακας που αποτελείται από ~N~ θετικούς ακέραιους αριθμούς, ~A_1~, ~A_2~, ~...~, ~A_N~. Σε μία κίνηση, ο παίκτης πρέπει να επιλέξει ακριβώς δύο στοιχεία του πίνακα, έστω ~A_x~ και ~A_y~, με ~x \neq y~, τα οποία να είναι είτε και τα δύο άρτια, είτε και τα δύο περιττά. Στη συνέχεια, τα διαγράφει από τον πίνακα και:

• Αν τα στοιχεία ήταν περιττά, τοποθετεί οπουδήποτε στον πίνακα τον αριθμό ~A_x + A_y + 7~, πληρώνοντας κόστος ~A_x + A_y + 7~.
• Αν τα στοιχεία ήταν άρτια, τοποθετεί οπουδήποτε στον πίνακα τον αριθμό ~A_x + A_y + 8~, πληρώνοντας κόστος ~A_x + A_y + 8~.

Σκοπός του παίκτη είναι να καταλήξει να έχει ακριβώς ένα στοιχείο, πληρώνοντας το ελάχιστο δυνατό συνολικό κόστος. Προκειμένου να μην μπορεί πάντοτε ο παίκτης να κερδίσει, ο Τάκης έχει συμπεριλάβει περιπτώσεις όπου το να καταλήξει κανείς σε ένα στοιχείο είναι αδύνατο. Τώρα είναι σειρά σας να παίξετε το παιχνίδι.

Πρόβλημα

Να γράψετε ένα πρόγραμμα σε μία από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, JAVA) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο mergegame2.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο mergegame2.out.

Αρχεία εισόδου (mergegame2.in)

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό ~N~: το αρχικό μέγεθος του πίνακα. Η δεύτερη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~A_1~, ~A_2~, ~...~, ~A_N~: τα αρχικά στοιχεία του πίνακα.

Αρχεία εξόδου (mergegame2.out)

Πρέπει να περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: το ελάχιστο συνολικό κόστος που χρειάζεται να πληρώσει ένας παίκτης για να καταλήξει με ακριβώς ένα στοιχείο, ή ~-1~ αν αυτό δεν είναι εφικτό.

Παραδείγματα αρχείων εισόδου - εξόδου:

Είσοδος:

3
2 8 6

Έξοδος:

48

Εξήγηση:

Ο Τάκης μπορεί να πετύχει συνολικό κόστος ~48~, που αποδεικνύεται ότι είναι το βέλτιστο δυνατό, με τις εξής κινήσεις:

1. ~\underline{2}~ ~8~ ~\underline{6}~ ~\rightarrow~ ~8~ ~\underline{16}~ (Κόστος: ~2+6+8=16~)
2. ~\underline{8} \; \underline{16}~ ~\rightarrow~ ~32~ (Κόστος: ~8+16+8=32~)

Είσοδος:

2
15 62

Έξοδος:

-1

Περιορισμοί

• ~1 \le N \le 200.000~
• ~1 \le A_i \le 10^9~

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

1. (12 βαθμοί) ~N = 2~
2. (21 βαθμοί) Όλα τα στοιχεία του ~A~ είναι ίσα μεταξύ τους και άρτια.
3. (20 βαθμοί) ~A_i = 2^{i-1}~ για κάθε ~i~ (όπου ~1 \le i \le N~).
4. (22 βαθμοί) ~N \le 5000~
5. (25 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί.

Παρατηρήσεις:

• Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
• Μέγιστος χρόνος εκτέλεσης: ~1~ sec.
• Μέγιστη διαθέσιμη μνήμη: ~64~ MB.
• Επικεφαλίδες στον πηγαίο κώδικα: Στην αρχή του πηγαίου κώδικά σας, θα πρέπει να χρησιμοποιήσετε τις παρακάτω επικεφαλίδες.

(* USER: username
LANG: PASCAL
TASK: mergegame2 *)

για κώδικα σε PASCAL

/* USER: username
LANG: C
TASK: mergegame2 */

για κώδικα σε C

/* USER: username
LANG: C++
TASK: mergegame2 */

για κώδικα σε C++

/* USER: username
LANG: Java
TASK: mergegame2 */

για κώδικα σε Java

Προσοχή: Η απάντηση μπορεί να υπερβαίνει το ~2^{32}~. Επίσης, φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν μεταφράζετε σε C++ ή Java.