## Token (Easy)

View as PDF

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

This problem is the easy version of the Token (Hard) problem. The easy version of the problem doesn't have the variable $$\mathbf{K}$$.

Ada wants to buy $$\mathbf{N}$$ different kinds of products. She is going to buy i'th product $$\mathbf{a_i}$$ times. The owner of the wholesale store offers Ada, a great plan. Here's the plan:

The store owner gives Ada $$\mathbf{2^N}$$ points. Ada will choose the unit price of each product, and it will be a positive integer. Selecting $$\mathbf{X}$$ $$(1\leq \mathbf{X}\leq\mathbf{N}$$, $$\mathbf{X}$$∈ $$Z^{+}$$) as the unit price for a product, will cost Ada $$\mathbf{2^{(N-X)}}$$ points. Ada can use her points as she wishes, provided that these rules are followed.

What is the minimum total cost Ada should pay to buy all the products she needs?

#### Input

• The first line contains 1 integer:
• $$2\leq\mathbf{N}\leq10^5$$ (Number of different kinds of products Ada wants to buy)
• The second line contains $$\mathbf{N}$$ integers:
• $$1\leq\mathbf{a_i}\leq10^5$$ (Amount of product i Ada wants to buy)

#### Output

1 positive integer (minimum price to pay)

#### Example

Input:

7
3 10 3 5 21 8 15

Output:

165

#### Explanation

• Ada has a total of $$2^{7}=128$$ points.

• unit price for 1st product($$a_i=3$$) was chosen as 4. $$2^{7-4}=8$$ points has been used. 120 left.
• unit price for 2nd product($$a_i=10$$) was chosen as 3. $$2^{7-3}=16$$ points has been used. 104 left.
• unit price for 3rd product($$a_i=3$$) was chosen as 4. $$2^{7-4}=8$$ points has been used. 96 left.
• unit price for 4th product($$a_i=5$$) was chosen as 3. $$2^{7-3}=16$$ points has been used. 80 left.
• unit price for 5th product($$a_i=21$$) was chosen as 2. $$2^{7-2}=32$$ points has been used. 48 left.
• unit price for 6th product($$a_i=8$$) was chosen as 3. $$2^{7-3}=16$$ points has been used. 32 left.
• unit price for 7th product($$a_i=15$$) was chosen as 2. $$2^{7-2}=32$$ points has been used. 0 left.
• $$3\cdot4+10\cdot3+3\cdot4+5\cdot3+21\cdot2+8\cdot3+1\cdot2=165$$