0.Luffy thăm bạn


Submit solution

Points: 2 (partial)
Time limit: 1.0s
Memory limit: 10M

Author:
Problem type

Xuân Mậu Tuất đã đến gần. Năm nay, Luffy quyết định bay từ đảo Zou đến Hà Nội để thăm bạn bè của mình. Vì muốn ở lại một thời gian dài nên Luffy quyết định xây một căn nhà để ở. Anh ta sẽ tìm vị trí căn nhà sao cho tổng khoảng cách từ căn nhà của mình đến nhà từng người bạn của mình là nhỏ nhất. Biết rằng một căn nhà có thể có nhiều người bạn của Luffy sống chung và các căn nhà đều nằm trên trục tọa độ Ox.

Hãy viết chương trình đưa ra tổng khoảng cách nêu trên.

Chú ý rằng Luffy có thể chọn bất cứ vị trí nào trên trục Ox để làm nhà ở (kể cả xây chồng lên nhà bạn mình).

Input

Dòng đầu chứa số nguyên N là số người bạn của Luffy.

Dòng tiếp theo bao gồm N số nguyên A_1, A_2, ..., A_n là vị trí căn nhà mà người bạn thứ i của Luffy đang sống.

Khoảng cách đi từ căn nhà i đến căn nhà j là: |A_i - A_j|

1 \le N \le 500

1 \le A_i \le 30000

Output

Một số nguyên dương duy nhất là tổng khoảng cách nhỏ nhất từ nhà của Luffy đến nhà các người bạn.

Example

Input:

2
3 5

Output:

2

Input:

2
2 2

Output:

0

Giải thích test 1: Luffy có thể chọn ở vị trí 3, 4, 5 đều thu được tổng nhỏ nhất là 2.

Giải thích test 2: Luffy có thể chọn ở vị trí 2 thu được tổng nhỏ nhất là 0.


Comments