Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

B. Not Even Close
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Potato King is plotting his next moves to bring a decisive victory in the Great Potato War! Manually planting and harvesting potatoes for $$$11$$$ hours a day is giving him carpal tunnel, so he's looking into trading with a group of $$$N$$$ ($$$2 \le N \le 1,000$$$) villagers to get potatoes. For each of the $$$N$$$ villagers, villager $$$i$$$ has an exchange rate of $$$P_i$$$ ($$$1 \le P_i \le 1,000$$$); that villager is willing to trade $$$P_i$$$ potatoes for an emerald, or one emerald for $$$P_i$$$ potatoes.

The Potato King can do some amount of trade operations. In a single trade, he first selects two villagers $$$i$$$ and $$$j$$$. Then, he spends $$$P_i$$$ potatoes to get an emerald from villager $$$i$$$, then spends that emerald to get $$$P_j$$$ potatoes from villager $$$j$$$. This results in a net gain of $$$P_j-P_i$$$ potatoes. Each villager may be selected no more than once; otherwise, the villagers may get suspicious and start to undergo mitosis. Note that the Potato King has enough potatoes initially to trade with any villager.

Given $$$N$$$ villagers where the $$$i$$$th villager buys or sells potatoes at the exchange rate of $$$P_i$$$ potatoes per emerald, find the maximum number of potatoes that the Potato King can gain!

Input

The first line consists of integer $$$N$$$ ($$$1 \le N \le 1,000$$$): the number of villagers. The second line consists of $$$N$$$ space-separated integers $$$P_1$$$ through $$$P_N$$$ ($$$1 \le P_i \le 1,000$$$): each villager's price.

Output

Output a single integer: the maximum amount of potatoes that the Potato King can gain after trading!

We have provided sample input parsing scripts in C++, Java, and Python below.

Examples
Input
5
4 2 3 1 5
Output
6
Input
6
1 1 4 2 3 4
Output
7
Input
1
67
Output
0
Input
11
84 69 67 72 78 79 66 76 65 68 69
Output
54
Note

In the first testcase, the Potato King can do two trades. First, he trades with the second and fifth villager, spending two potatoes to get five potatoes. Next, he trades with the fourth and first villagers, spending one potato to get four potatoes. In total, he gains a net $$$6$$$ potatoes. Note that this is not the only possible ordering that gains $$$6$$$ potatoes!