Cân bằng que diêm

Petya có $k$ que diêm được đặt trong $n$ hộp diêm xếp thành một hàng từ trái sang phải. Số $k$ luôn chia hết cho $n$.

Petya muốn mọi hộp đều chứa cùng một số que diêm. Trong một lần di chuyển, cậu ấy lấy đúng một que diêm từ một hộp và bỏ sang một hộp kề bên (hộp liền trái hoặc liền phải). Chuyển một que diêm đi xa hơn một hộp vì thế tốn nhiều lần di chuyển.

Hãy tính số lần di chuyển ít nhất để tất cả các hộp có số que diêm bằng nhau.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số hộp diêm.
• Dòng thứ hai chứa $n$ số nguyên không âm, số thứ $i$ là số que diêm trong hộp thứ $i$.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng số lần di chuyển ít nhất.

Ràng buộc

• $1\le n\le 50000$
• $0\le a_i\le {10}^9$
• Tổng số que diêm chia hết cho $n$.

Ví dụ