Cho mảng ~a~ có ~n~ phần tử nguyên dương, có thể thực hiện thao tác sau vô số lần hoặc không lần nào: Chọn 2 phần tử khác nhau bất kì trong mảng, gán lại giá trị cho phần tử lớn hơn bằng giá trị tuyệt đối hiệu 2 phần tử. Hỏi tổng nhỏ nhất có thể của mảng ~a~ sau khi thực hiện các thao tác trên là bao nhiêu?

Input

• Dòng đầu tiên gồm số nguyên dương ~1 \le n \le 10^5~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~1 \le a_i \le 10^9~ là các phần tử của mảng ~a~.

Output

• In ra tổng nhỏ nhất có thể.

Sample Test

Input:

2
1 2

Output:

2