Pasha is also against "tails"?

Pasha will perfectly manage to study exactly one topic in mathematics before the exam, but there are many tasks on the exam and from different topics, so what to do?

Pasha has learned to change the topics of exam tasks. So he won't fail.

If the topic of the task is $a_i$, then in one operation Pasha can change the topic of the task in one of the following ways:

• $a_i:=a_i+1$;

• $a_i:=a_i-1$.

In other words, in one operation Pasha can choose some element of the array and change it by one.

Pasha was lucky to find exam tickets in the e-learning system, there are a total of $n$ questions, each of which is characterized by a single number $a_i$. However, things are not so smooth, so to minimize the chance of getting caught, he must make the minimum possible number of operations.

Your task is to transform all tasks into tasks of one topic with the minimum number of operations.

Input

The first line contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the number of tasks.

The second line contains $n$ integers $a_1,\dots ,a_n$ ($1\le a_i\le 10^9$) — the topics of the tasks.

Output

Output a single number — the minimum number of operations.

Examples

Note

In the first test, the optimal solution will be to perform the following operations:

1. apply the operation to the 2nd task: assign $a_2:=a_2-1$ after this the array will become equal to $[2,2,5,1,2]$;

2. apply the operation to the 3rd task: assign $a_3:=a_3-1$ after this the array will become equal to $[2,2,4,1,2]$;

3. apply the operation to the 3rd task: assign $a_3:=a_3-1$ after this the array will become equal to $[2,2,3,1,2]$;

4. apply the operation to the 3rd task: assign $a_3:=a_3-1$ after this the array will become equal to $[2,2,2,1,2]$;

5. apply the operation to the 4th task: assign $a_4:=a_4+1$ after this the array will become equal to $[2,2,2,2,2]$;

It can be shown that obtaining an answer less than $5$ is not possible.

Scoring

In this problem, there are conditional blocks. If your solution works correctly for certain constraints, it will receive a certain number of points. Note that each test is graded individually.

1. ($20$ points): $a_i\le 100$, $n\le 100$;

2. ($40$ points): $n\le 1000$;

3. ($40$ points): without additional constraints.