Merge Game 2

The merge game that Takis created during last year's Phase ~B~ attracted many people to his pizzeria, but it turned out to be particularly difficult for his younger visitors. Therefore, Takis decided to create an easier game. (Note: You do not need to read or solve last year's problem to solve this one; they are independent of each other.)

The player is given an array consisting of ~N~ positive integers, ~A_1~, ~A_2~, ~...~, ~A_N~. In one move, the player must choose exactly two elements of the array, say ~A_x~ and ~A_y~, with ~x \neq y~, which must be either both even or both odd. Then, the player removes them from the array and:

• If the elements were odd, the player inserts the number ~A_x + A_y + 7~ anywhere in the array, paying a cost of ~A_x + A_y + 7~.
• If the elements were even, the player inserts the number ~A_x + A_y + 8~ anywhere in the array, paying a cost of ~A_x + A_y + 8~.

The player's goal is to end up with exactly one element while paying the minimum possible total cost. To ensure that the player cannot always win, Takis has included cases in which ending up with one element is impossible. Now it is your turn to play the game.

Problem

Write a program in C++ that reads the input data from the file mergegame2.in and prints the results to the file mergegame2.out.

Input Files (mergegame2.in)

The first line contains an integer ~N~: the initial size of the array. The second line contains ~N~ integers ~A_1~, ~A_2~, ~...~, ~A_N~: the initial elements of the array.

Output Files (mergegame2.out)

The output must contain a single line with an integer: the minimum total cost a player must pay to end up with exactly one element, or ~-1~ if this is not possible.

Sample Input - Output Files:

Input:

3
2 8 6

Output:

48

Explanation:

Takis can achieve a total cost of ~48~, which can be proven to be optimal, with the following moves:

1. ~\underline{2}~ ~8~ ~\underline{6}~ ~\rightarrow~ ~8~ ~\underline{16}~ (Cost: ~2+6+8=16~)
2. ~\underline{8} \; \underline{16}~ ~\rightarrow~ ~32~ (Cost: ~8+16+8=32~)

Input:

2
15 62

Output:

-1

Constraints

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

Subtasks:

1. (12 points) ~N = 2~
2. (21 points) All elements of ~A~ are equal to one another and even.
3. (20 points) ~A_i = 2^{i-1}~ for every ~i~ (where ~1 \le i \le N~).
4. (22 points) ~N \le 5000~
5. (25 points) There are no further constraints.

Notes:

• Formatting: In both the input and the output, each line ends with a newline character.
• Maximum execution time: ~1~ sec.
• Maximum available memory: ~64~ MB.

Warning: The answer may exceed ~2^{32}~ and, in general, you may need to perform operations with numbers larger than those that can be represented by the basic int type. Also, make sure to read the input and print the output efficiently in problems that require it.