E-Evil Capitalist_2023年第六届广西大学生程序设计竞赛（正式赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Today Colin and Eva learned what is exploitation in the course 'Basic Principles of Marxism'. At night, Colin had a dream where he was a poor worker, cruelly exploited by capitalist Eva without realizing it at all...
Assuming you are an evil capitalist with $n$ exploited workers under your command, numbered from $1$ to $n$ . The current salary of worker with number $i$ is $a_i$ yuan. Under your strict supervision, workers cannot tell each other their salaries. You thought the good days would continue like this, but the workers increasingly felt exploited, so they decided to strike and protest against you!

Without the labor of workers, there wouldn't be a luxurious life for you. So you decide to raise their salaries in an appropriate way to stop them from protesting. At first, every worker is unsatisfied. You need to organize several two-person chats to make everyone satisfied, or only one person unsatisfied - at this point, there will be nobody who wants to protest against you with him.

To organize a two-person chat, you need to choose two unsatisfied workers $x,y$ , then allow them to tell each other their salaries without penalty temporarily:

if $a_x=a_y$ (which means they have the same salary), both of the two workers will feel that they have not been mistreated and both will become satisfied .
if $a_x>a_y$ , then worker $x$ will become satisfied. However, worker $y$ will realize that he has been treated differently, so you need to increase his salary to $a_x$ (which means you have to pay him $a_x-a_y$ yuan, then let $a_y=a_x$ ), and worker $y$ still remains unsatisfied.
Similarly, If $a_y > a_x$ then worker $y$ will become satisfied. However you have to pay worker $x$ $a_y-a_x$ yuan, then let $a_x=a_y$ , and worker $x$ still remains unsatisfied .

But as an evil capitalist, you want to know at least how much money you need to pay them to achieve your goal.

输入描述:

The first line contains one integer  , representing the number of workers.

The second line contains  integers  ;  represents the current salary of the -th worker.

输出描述:

A single integer, represents the minimum amount of money you need to spend.

示例1

输入

复制

4
100 101 1 101

输出

复制

说明

You can first let worker  talk with worker  , then worker  will become satisfied, and you need to pay  yuan to worker  , then  becomes  .

Then you can let worker  talk with worker  , since they have the same salary, so both of them will become satisfied.

Then only the worker  is not satisfactory, you have already achieved your goal.