Pasha is also against "tails"?#19

Pasha is also against "tails"?

1 second
256 megabytes
Easy

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:

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 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 (1\le n\le 2\cdot 10^5) — the number of tasks.

The second line contains 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

Example

Loading
Loading

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 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. ( points): a_i\le 100, n\le 100;

  2. ( points): n\le 1000;

  3. ( points): without additional constraints.