Tìm vị trí

Gần đường cao tốc (coi như một đường thẳng nằm ngang) có $N$ ngôi làng. Từ ngôi làng thứ $i$, người ta làm một con đường dân sinh nối tới điểm $x_i$ trên đường cao tốc. Do các con đường dân sinh này có độ dài không đáng kể nên người ta tính khoảng cách di chuyển giữa ngôi làng thứ $i$ và ngôi làng thứ $j$ là $|x_i - x_j|$. Công ty vận chuyển ABC Expres đang nghiên cứu khảo sát để đặt một bưu cục tại một ngôi làng nào đó trong số các ngôi làng trên. Phương án thứ $i$, bưu cục sẽ được đặt tại ngôi làng thứ $i$ với tổng khoảng cách từ các ngôi làng khác là:

$P_i = |x_1 - x_i| + |x_2 - x_i| + |x_3 - x_i| + \dots + |x_N - x_i|$

Yêu cầu: Hãy viết chương trình xác định tổng khoảng cách tất cả các ngôi làng tới bưu cục được chọn trong từng phương án.

Đọc vào từ file POST.INP

• Dòng đầu tiên chứa số nguyên dương $N$ $(N \le 10^5)$.
• Dòng thứ hai chứa $N$ số nguyên dương $x_1, x_2, \dots, x_N$ $(x_i \le 10^6$ với $\forall i = 1, 2, \dots, N)$.

Ghi ra file POST.OUT gồm $N$ số nguyên theo thứ tự $P_1, P_2, P_3, \dots, P_N$. Các số được đưa ra cách nhau một dấu cách.

• Có 40% test tương ứng 40% số điểm có $N \le 10^3; x_1 \le x_2 \le \dots \le x_N \le 10^2$
• Có 20% test khác tương ứng 20% số điểm có $N \le 10^5; x_1 \le x_2 \le \dots \le x_N \le 10^2$
• Có 20% test khác tương ứng 20% số điểm có $N \le 10^5; x_1 \le x_2 \le \dots \le x_N \le 10^6$
• Có 20% test còn lại tương ứng 20% số điểm không có ràng buộc gì thêm.