LQDOJ Contest #8 - Bài 2 - Tất Niên

Xem PDF
Tác giả:
shiba
Dạng bài
Điểm: 800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Phường LQDOJ Có \(N\) gia đình sinh sống. Nhà thứ \(i\) có tọa độ là \(x_i\).

Chủ tịch UBND phường quyết định tổ chức lễ tất niên cuối năm và tất cả các gia đình đều phải tham gia lễ tất niên này. Lễ tất niên này có thể tổ chức tại một ngôi nhà \(m\) bất kì (\(m\) phải là số nguyên), nhà thứ \(i\) cần phải trả \((x_i - m)^2\) đồng.

Yêu cầu: Bạn hãy lập trình tính tổng số tiền ít nhất có thể mà tất cả các nhà phải trả.

Input

  • Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 10^6)\).
  • Dòng tiếp theo chứa \(N\) số nguyên dương \(x_1,x_2,...,x_N\) \((1 \le x_i \le 10^6)\).

Output

  • In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): Có \(N \le 5000\).

  • Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
3
1 2 3
Output 
2
Note
  • Nếu ta chọn ngôi nhà có tọa độ \(m = 2\) thì nhà thứ \(1\) cần phải trả \((1-2)^2 = 1\) đồng, nhà thứ hai cần phải trả \((2-2)^2 = 0\) đồng, nhà thứ ba phải trả \((3-2)^2 = 1\) đồng. Vậy số tiền tối thiểu cần phải trả của tất cả các nhà là \(1+0+1 = 2\) đồng.

Bình luận