Cho dãy số nguyên dương ~n~ phần tử. Ta có thể thực hiện các thao tác sau với không giới hạn số lần: Chọn ra 2 số khác nhau bất kì trong dãy. Giảm giá trị số lớn đi một lượng bằng độ lớn số bé. Làm sao để tìm ra tổng các phần tử của dãy là nhỏ nhất

Input

• Dòng đầu ghi số ~n~ ~(1 \leq n \leq 10^5)~
• Dòng tiếp theo là ~n~ số nguyên ~a_i~ ~(1 \leq a_i \leq 10^5)~

Output

• In ra đáp án

Example

Input

4
2 5 3 4

Output

4