|Codeforces Round #186 (Div. 2)|
Ilya is a very good-natured lion. He likes maths. Of all mathematical objects, his favourite one is matrices. Now he's faced a complicated matrix problem he needs to solve.
He's got a square 2n × 2n-sized matrix and 4n integers. You need to arrange all these numbers in the matrix (put each number in a single individual cell) so that the beauty of the resulting matrix with numbers is maximum.
The beauty of a 2n × 2n-sized matrix is an integer, obtained by the following algorithm:
As you can see, the algorithm is recursive.
Help Ilya, solve the problem and print the resulting maximum beauty of the matrix.
The first line contains integer 4n (1 ≤ 4n ≤ 2·106). The next line contains 4n integers ai (1 ≤ ai ≤ 109) — the numbers you need to arrange in the 2n × 2n-sized matrix.
On a single line print the maximum value of the beauty of the described matrix.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
1 2 3 4
Consider the second sample. You need to arrange the numbers in the matrix as follows:
Then the beauty of the matrix will equal: 4 + 1 + 2 + 3 + 4 = 14.