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 2^{n} × 2^{n}-sized matrix and 4^{n} 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 2^{n} × 2^{n}-sized matrix is an integer, obtained by the following algorithm:  Find the maximum element in the matrix. Let's denote it as m.  If n = 0, then the beauty of the matrix equals m. Otherwise, a matrix can be split into 4 non-intersecting 2^{n} - 1 × 2^{n} - 1-sized submatrices, then the beauty of the matrix equals the sum of number m and other four beauties of the described submatrices. 

As you can see, the algorithm is recursive.

Help Ilya, solve the problem and print the resulting maximum beauty of the matrix.


-----Input-----

The first line contains integer 4^{n} (1 ≤ 4^{n} ≤ 2·10^6). The next line contains 4^{n} integers a_{i} (1 ≤ a_{i} ≤ 10^9) — the numbers you need to arrange in the 2^{n} × 2^{n}-sized matrix.


-----Output-----

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.


-----Examples-----
Input
1
13

Output
13

Input
4
1 2 3 4

Output
14



-----Note-----

Consider the second sample. You need to arrange the numbers in the matrix as follows:

1 2

3 4



Then the beauty of the matrix will equal: 4 + 1 + 2 + 3 + 4 = 14.

Source: codeforces | Difficulty: MEDIUM
Tags: Greedy algorithms

Sorting

Implementation

Constructive algorithms


Solutions:
n = int(input())
a = list(map(float, input().split()))
a.sort(reverse=True)
res = 0
while a:
	res += sum(a)
	a = a[:len(a) // 4]
print(int(res))


def arr_inp():
	return [float(x) for x in input().split()]

def solve(n):
	nonlocal s
	if n == 1:
		s += a[0]
		return
	else:
		solve(n // 4)
	s += sum(a[:n])
(n, a, s) = (int(input()), arr_inp(), 0)
a = sorted(a, reverse=True)
solve(n)
print(int(s))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
from math import log
l = list(map(int, input().split()))
l.sort(reverse=True)
a = int(log(n, 4))
if n == 1:
	print(l[0])
else:
	ans = l[0] * (a + 1)
	i = 1
	c = 0
	while i < n:
		if a > 1:
			for j in range(4 ** c * 3):
				ans += l[i + j] * a
			a -= 1
			i += 4 ** c * 3
			c += 1
		else:
			ans += l[i]
			i += 1
	print(ans)


import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
nums = list(map(int, input().split()))
nums.sort(reverse=True)
exp = 0
left = 0
res = 0
j = 0
while n != 0:
	j = n // 4
	res += sum(nums[j:n]) * (exp + 1)
	n = j
	exp += 1
print(res)


n = int(input())
arr = list(map(float, input().split()))
if n == 1:
	print(int(arr[0]))
	exit()
arr.sort(reverse=True)
res = 0
while arr:
	res += sum(arr)
	arr = arr[:len(arr) // 4]
print(int(res))


def arr_inp():
	return [float(x) for x in stdin.readline().split()]

def solve(n):
	global s
	if n == 1:
		s += a[0]
		return
	else:
		solve(n // 4)
	s += sum(a[:n])
from sys import *
(n, a, s) = (int(input()), sorted(arr_inp(), reverse=True), 0)
solve(n)
print(int(s))


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7
from bisect import bisect_left

def solve():
	X = getInt()
	A = getInts()
	N = int(math.log2(X) // 2)
	A.sort()
	if N == 0:
		return A[0]
	ans = (N + 1) * A.pop()
	for i in range(3):
		ans += N * A.pop()
	curr = 12
	num = N - 1
	while A:
		for i in range(curr):
			ans += num * A.pop()
		curr *= 4
		num -= 1
	return ans
print(solve())


n = int(input())
lis = list(map(float, input().split()))
ans = 0
lis.sort(reverse=1)
while lis:
	ans += sum(lis)
	lis = lis[:len(lis) // 4]
print(int(ans))


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def main():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a.reverse()
	ans = 0
	i = 1
	while i <= n:
		ans += sum(a[0:i])
		i *= 4
	print(ans)
	return
main()


import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from math import log2
n = int(input())
l = sorted(map(int, input().split()), reverse=True)
t = pow(n, 0.5)
c = int(log2(t)) + 1
ca = c
ans = 0
cc = 1
for i in range(n):
	if i + 1 > cc:
		cc *= 4
		ca -= 1
	ans += ca * l[i]
sys.stdout.write(str(ans) + '\n')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def main():
	n = int(input())
	numbers = [int(c) for c in input().split()]
	numbers.sort(reverse=True)
	acc = [0]
	for e in numbers:
		acc.append(acc[-1] + e)
	i = 1
	res = 0
	while i <= n:
		cnt = n // i
		res += acc[cnt]
		i *= 4
	print(res)
main()


from sys import stdin
n = int(stdin.readline())
arr = list(map(float, stdin.readline().split()))
if n == 1:
	print(int(arr[0]))
	return
arr.sort(reverse=True)
res = 0
while arr:
	res += sum(arr)
	arr = arr[:len(arr) // 4]
print(int(res))


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
MOD = 1000000007

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
n = Int()
a = sorted(array(), reverse=True)
k = int(log(n, 4)) + 1
ans = 0
end = 1
c = 0
for i in range(n):
	if i == end:
		k -= 1
		c += 1
		end = 4 ** c
	ans += k * a[i]
print(ans)