409667: GYM103677 E Festa des Vermar

Every year in September, the town of Binissalem, Spain celebrates Festa des Vermar, a two-week-long festival starring – what else? – grapes. The celebration includes everything from wine-parades to grape-stomping.

You, in particular, are interested in the grape battle, which is exactly what it sounds like. You know that to be effective in the grape battle, you should choose the juiciest grapes to throw. Unfortunately, your brother gets to pick which grapes he wants first.

There are $$$N$$$ grapes in a row, with juiciness $$$a_1, a_2, ..., a_N$$$. Grape distribution happens as follows: your brother selects the first two grapes, chooses the juiciest one, and then gives you the remaining grape. He then selects the next two grapes and does the same thing, then the next two, and so on until all the grapes have been distributed.

Luckily, while your brother wasn't looking, you managed to change the order of the grapes in the row. If you permute the grapes optimally, what will be the maximum total juiciness of all the grapes you receive?

Note: Watch out for integer overflows.

The first line contains an integer $$$N$$$, denoting the number of grapes. ($$$2 \le N \le 10^5$$$) It is guaranteed that $$$N$$$ will be divisible by 2.

The second line contains $$$N$$$ integers $$$a_1, a_2, ... , a_N$$$, denoting the juiciness of the grapes. ($$$1 \le a_i \le 10^9$$$)

Output one integer, the maximum total juiciness of the grapes you receive if you change the order of the grapes optimally.

6
1 2 4 5 2 7

8

In the first example, you can rearrange the grapes to form the following sequence: $$$[2, 4, 1, 2, 7, 5]$$$. The total juiciness is then 8, corresponding to grapes with juiciness 2, 1, and 5. It can be proven that this is the maximum possible total juiciness (although different permutations also exist that achieve this total juiciness).