Có ~n~ con kiến đang đứng trên 1 đường thẳng, con kiến thứ ~i~ đứng tại vị trí ~a_i~. Hãy tìm tổng khoảng cách của ~n~ con kiến so với từng vị trí ~a_i~ theo thứ tự input.

Input

• Dòng đầu tiên gồm ~n~ (~1 \leq n \leq 10^6~)
• Dòng tiếp theo gồm ~n~ số, số thứ ~i~ là tọa độ ~a_i~ của con kiến thứ ~i~ (~1 \leq a_1 < a_2 < \ldots < a_n \leq 10^9~)

Output

Một dòng duy nhất chứa ~n~ số ứng với ~n~ đáp án cần tìm

Ràng buộc

• ~50\%~ số test ứng với ~50\%~ số điểm có ~n \leq 10^3~
• ~50\%~ số test còn lại không có ràng buộc gì thêm

Sample Test

Input

5
1 2 3 4 5

Output

10 7 6 7 10

Giải thích

• Khoảng cách của từng con kiến so với vị trí ~a_1=1~ lần lượt là: ~0,1,2,3,4~ nên đáp án là ~0+1+2+3+4=10~
• Khoảng cách của từng con kiến so với vị trí ~a_2=2~ lần lượt là: ~1,0,1,2,3~ nên đáp án là ~1+0+1+2+3=7~
• Khoảng cách của từng con kiến so với vị trí ~a_3=3~ lần lượt là: ~2,1,0,1,2~ nên đáp án là ~2+1+0+1+2=6~