Mr. Thảo là một học sinh giỏi, được nhiều bạn mến mộ. Thế nhưng, trong dịp Tết vừa qua, vì mải ăn món mứt dâu ngon tuyệt do mẹ cậu làm, kết quả là bị đau bụng suốt mấy ngày liền, khi cậu ta khỏi bệnh cũng chính là lúc hết Tết. Lúc này Mr. Thảo mới sực nhớ ra bài tập Tết mà thầy giao, bình thường đó chỉ là những bài tập cỏn con đối với cậu ấy, thế nhưng giờ đau bụng như thế này thì đến đọc đề còn không nỗi huống chi là làm :(( Các bạn HBCoders hãy giúp Mr. Thảo giải bài tập để không bị thầy phạt ngày đầu năm nhé.

Đề bài như sau:

Cho dãy n số nguyên dương a₁, a₂, a₃, .., a_n

Có thể thực hiện thao tác sau đây trên dãy:

- Chọn ra hai số bất kì trong dãy

- Giảm giá trị số lớn hơn đi một lượng bằng giá trị của số nhỏ hơn

Có thể thực hiện số lượng thao tác tùy ý thích sao cho tổng giá trị các phần tử của dãy là nhỏ nhất

Input

Dòng đầu tiên chứa số nguyên dương n (n <= 10⁵)

Dòng tiếp theo chứa n số nguyên a1, a2, ..., an (1 <= a_i <= 10⁵)

Output

Một dòng duy nhất là tổng nhỏ nhất của dãy sau một số thao tác.