Discounted Milk Tea Purchase

A milk tea shop is running a special promotion with the following rules:

• If you buy a cup of milk tea at its full price, you receive a discount coupon.
• If you buy a cup of milk tea using discount coupon(s), you do not receive a coupon for that purchase.
• Each discount coupon can reduce the price by \(1\) unit of money.
• You can use an arbitrary number of coupons to purchase a cup, but no change is given. In other words, when using coupons for a cup with price \(a\), you can use at most \(a\) coupons.

Little F plans to buy \(n\) cups of milk tea whose prices are \(a_1, a_2, \dots, a_n\). He may purchase these cups in any order. Initially he has no coupons. When he buys a cup at full price he earns a coupon (which may later be used to discount other cups), and when he buys a cup using coupon(s) he does not earn any coupon.

Your task is to calculate the minimum total amount of money Little F must spend so that he can buy all \(n\) cups.

Note: It may be optimal to sometimes purchase a cup at full price (despite not using coupons) in order to earn coupons to reduce the cost of other cups.

Hint: If Little F decides to buy \(k\) cups at full price and the remaining \(n-k\) with coupons, then he will earn \(k\) coupons in total, while for each cup bought with coupons the maximum discount it can receive is its price \(a_i\). Using an optimal coupon allocation on the \(n-k\) cups (assigning coupons primarily to the more expensive ones), the total discount is \(\min\Big( k, \sum_{i\in T} a_i \Big)\) where \(T\) denotes the set of cups bought with coupons. Hence, the total spending will be \[ \text{TotalCost} = \sum_{i=1}^n a_i - \max_{0\le k\le n} \min\Big( k, \sum_{i\in T_k} a_i \Big), \] with an appropriate choice of the set \(T_k\). A simple way to solve the problem is to sort the prices and try all valid splits.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)), representing the number of milk tea cups.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)), where \(a_i\) is the price of the \(i\)-th cup.

outputFormat

Output a single integer, the minimum total cost required to purchase all \(n\) cups.

sample

1
5

5