Bill’s Cookie Addiction

Problem Statement:

Breaking News. A sting operation has revealed ever since his divorce, ex-richest-man-on-earth, Bill Gates, has developed a strong addiction for girl scout cookies. If Bill has eaten j cupcakes so far, after eating a scout cookie with c calories he must walk at least $2^j * c$ miles to maintain his weight. But Bill is a very lazy person and chooses to eat the cookies in an order such that he has to walk the least number of miles. Help Bill find the least number of miles he must walk to maintain his weight.

Constraints:

Subtask 1:

• 1 ≤ N ≤ 9

Subtask 2:

• 1 ≤ N ≤ 10⁹

Input Format:

• The first line contains an integer N
• The second line contains N space seperated integers representing the calories in each of the N cookies

Output Format:

• A single integer representing the minimum number of miles Bill Gates has to walk

Sample input:

3 1 3 2 

Sample output:

11