Là một sinh viên chăm chỉ, Long rất thích tìm tòi các bài toán hay để giải để nâng cao kiến thức và thoả mãn đam mê lập trình của mình. Một hôm, Long gặp một bài toán rất thú vị và muốn đưa lên đây để các bạn giải cùng. Đề bài được phát biểu như sau:

Cho một mảng gồm ~n~ số nguyên dương ~a_0, a_1, ..., a_{n-1}~ và giá trị ~f_i~ được định nghĩa như sau: $$\displaystyle f_i = \sum^{n - 1}_{j = 0} |a_i - a_j| $$

Nhiệm vụ của bạn là tìm giá trị ~min(f_0, f_1, ..., f_{n - 1})~

Input

• Dòng đầu tiên chứ số nguyên dương ~n~ là số lượng phần tử của mảng (~1 \le n \le 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_0, a_1, ..., a_{n-1}~ ~(1 \le a_0, a_1, ..., a_{n-1} \le 10^9)~.

Output

• Dòng duy nhất chứa một số nguyên dương là giá trị thoả mãn yêu cầu đề bài.

Scoring

• Subtask 1 (50% số điểm): ~1 \le n \le 10^3~.
• Subtask 2 (50% số điểm): ~1 \le n \le 10^6~.

Samples

Sample Input

5
3 2 5 9 8

Sample Output

12

Notes

Trong ví dụ, các giá trị ~f_i~ có giá trị như sau:

• ~f_0 = \sum^{n - 1}_{j = 0} |a_0 - a_j| = |3 - 3| + |3 - 2| + |3 - 5| + |3 - 9| + |3 - 8| = 14~.
• ~f_1 = \sum^{n - 1}_{j = 0} |a_1 - a_j| = |2 - 3| + |2 - 2| + |2 - 5| + |2 - 9| + |2 - 8| = 17~.
• ~f_2 = \sum^{n - 1}_{j = 0} |a_2 - a_j| = |5 - 3| + |5 - 2| + |5 - 5| + |5 - 9| + |5 - 8| = 12~.
• ~f_3 = \sum^{n - 1}_{j = 0} |a_3 - a_j| = |9 - 3| + |9 - 2| + |9 - 5| + |9 - 9| + |9 - 8| = 18~.
• ~f_4 = \sum^{n - 1}_{j = 0} |a_4 - a_j| = |8 - 3| + |8 - 2| + |8 - 5| + |8 - 9| + |8 - 8| = 15~.

Như vậy ~min(f_0, f_1, f_2, f_3, f_4) = 12~.