The treasure of a country far away is initially empty. Afterwards, the officials of the treasure acquire some jewels (each one with some value) and add them to the treasure one by one.

According to an old tradition, the king of that country has the right to choose and keep for himself up to two thirds of the jewels. Since the king may need to run away from the country at any moment, he always needs to know in an efficient way the maximum total value of the jewels that he can take with him. Can you help the king?

Input

Input consists of several cases.
Every case begins with the number n of jewels acquired by the treasure.
Follow the value of the n jewels,
in the order in which they are obtained.
Assume 1 ≤ n ≤ 10^{4},
and that the values are integer numbers between 1 and 10^{9}.

Output

For every case, and after every acquired jewel, print the maximum total value of the jewels that the king can choose. Print a line with 10 dashes after every case.

Public test cases

**Input**

6 10 42 20 23 1000 15 8 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 8 7 7 6 6 7 7 6 6

**Output**

0 42 62 65 1065 1085 ---------- 0 1000000000 2000000000 2000000000 3000000000 4000000000 4000000000 5000000000 ---------- 0 7 14 14 21 28 28 34 ----------

Information

- Author
- Salvador Roura
- Language
- English
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++