Bỏ qua đến nội dung

Tổng nhỏ nhất

Mã bài: spit0039 Nhóm: SPIT Dạng bài: Undefined

Giới hạn thời gian
1,0 s
Giới hạn bộ nhớ
256 MB
Điểm
10một phần
Tỉ lệ AC
31,2%
Người giải
38

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.

Bình luận