CF335F.Buy One, Get One Free

A nearby pie shop is having a special sale. For each pie you pay full price for, you may select one pie of a strictly lesser value to get for free. Given the prices of all the pies you wish to acquire, determine the minimum total amount you must pay for all of the pies.

附近的一家派饼店正在举行特别促销活动。对于你按全价购买的每块派饼，你可以额外选择一块价格严格更低的派饼免费获取。已知你想购买的所有派饼的价格，请计算你为获得所有这些派饼所需支付的最低总金额。

Input will begin with an integer n (1 ≤ n ≤ 500000), the number of pies you wish to acquire. Following this is a line with n integers, each indicating the cost of a pie. All costs are positive integers not exceeding 109.

输入的第一行是一个整数 $n$（$1 \leq n \leq 500000$），表示你希望获得的派的数量。接下来的一行包含 $n$ 个整数，每个整数表示一个派的成本。所有成本均为不超过 $10^9$ 的正整数。

Print the minimum cost to acquire all the pies.

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.

输出获取所有派的最小花费。

请注意，在 C++ 中不要使用 %lld 说明符读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。

In the first test case you can pay for a pie with cost 5 and get a pie with cost 4 for free, then pay for a pie with cost 5 and get a pie with cost 3 for free, then pay for a pie with cost 4 and get a pie with cost 3 for free.

In the second test case you have to pay full price for every pie.

在第一个测试用例中，你可以支付一个价格为 5 的派的费用，并免费获得一个价格为 4 的派；然后支付另一个价格为 5 的派的费用，并免费获得一个价格为 3 的派；最后支付一个价格为 4 的派的费用，并免费获得一个价格为 3 的派。

在第二个测试用例中，你必须为每个派支付全额费用。