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 a1, a2, a3, .., an
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 <= 105)
Dòng tiếp theo chứa n số nguyên a1, a2, ..., an (1 <= ai <= 105)
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.
Với dãy số 4 2 1, ta lần lượt thực hiện các thao tác như sau
- Chọn số 4 và 2, giảm 4 đi 2, khi đó dãy trở thành 2 2 1
- Chọn số 2 và 1, giảm 2 đi 1, khi đó dãy trở thành 2 1 1
- Chọn số 2 và 1, giảm 2 đi 1, khi đó dãy trở thành 1 1 1
Lúc này không thể thực hiện thao tác được nữa do giá trị các phần tử trong dãy đều bằng nhau, tổng nhỏ nhất của dãy là 3