The Hobanwoo Merchant's Strange Quality Calculation

The Hobanwoo, a specialty product of Kyungpook National University, is graded with a number according to its quality. Hobanwoo merchants want to sell N Hobanwoo. A Hobanwoo can be sold individually, but it can also be sold in a bundle. A bundle here means any subset of the Hobanwoo.

When selling a single Hobanwoo, the old calculation method sets the price equal to its quality.

So there was no difference in the total amount a merchant could earn whether selling in bundles or individually.

But the Hobanwoo merchants are greedy, so they hold a meeting to find a way to receive more money. In the middle of it, the Hobanwoo merchants developed a new quality calculation method!

When selling Hobanwoo as a bundle, the quality of every Hobanwoo is set to the 'median' of the bundle. Here, if the bundle has an even number of Hobanwoo, the median is defined as the (bundle size/2+1)-th Hobanwoo when the Hobanwoo in the bundle are sorted by quality, and if the bundle has an odd number, it is defined as the ((bundle size+1)/2)-th Hobanwoo.

They succeeded in creating the new calculation method, but with so many Hobanwoo, the merchants began to get confused about how to bundle them, and they were failing to earn the maximum profit from their business. For the Hobanwoo merchants, let's write a program that calculates the maximum profit that can be earned by selling the Hobanwoo!

The first line gives the number of Hobanwoo N (1 ≤ N ≤ 100,000).

The second line gives N space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 1,000), and these numbers represent the quality of each Hobanwoo.

Output the maximum profit that can be earned by selling all the Hobanwoo.

If the qualities of the Hobanwoo in some bundle are [1, 2, 3, 4], the quality of every Hobanwoo is calculated as the median, 3. So the total price of this bundle is 3 × 4 = 12.

If the qualities are [6, 3, 9], the quality of every Hobanwoo is calculated as the median, 6. So the total price of this bundle is 6 × 3 = 18.