Sự kiện Halloween sắp tới của trường được tổ chức với quy mô rất hoành tráng, công tác chuẩn bị của các lớp cũng đang được gấp rút tiến hành. Bạn Ngọc được bạn Hoàng giao cho một nhiệm vụ là lên ý tưởng, tổ chức một số hoạt động cho lớp. Sau nhiều đêm suy nghĩ miệt mài ngoài việc đã giảm được vài cân, Ngọc đã nghĩ ra một ý tưởng đó là chia \(n\) các thành viên trong lớp ra để đi phát kẹo. Mỗi túi kẹo của từng thành viên đang có sẵn \(a_{i}\) chiếc kẹo (thành viên thứ \(i\)), Ngọc muốn mỗi túi kẹo của các thành viên phải bằng nhau và số kẹo được phát đi lớn nhất có thể. Hãy giúp Ngọc giải quyết vấn đề nhé

Đầu vào:

• Dòng đầu tiên của mỗi trường hợp chứa số nguyên \(n\) \((1 \leq n \leq 100000)\), số thành viên trong lớp
• Dòng thứ hai gồm \(n\) số nguyên , ,…, \((0 \leq a_{i}\leq 10^9)\), số kẹo có trong túi mỗi thành viên thứ \(i\).

Đầu ra:

Số nguyên \(S\), số kẹo tối thiểu Ngọc phải thêm vào để các túi kẹo bằng nhau

Ví dụ:

Input

5
0 2 4 3 5

Output

11