Cho một dãy số ~N~ số nguyên dương ~A_1, A_2, ..., A_N~.

Xét thao tác: chọn hai số nguyên ~i, j~ ~(1 \leq i, j \leq N, i \neq j, A_i, A_j > 0)~ và cập nhật ~A_i := A_i - A_j~. Sau một số thao tác, dãy ~A~ chỉ còn duy nhất một số dương. Tìm giá trị nhỏ nhất có thể của số đó.

Input

Dòng đầu tiên gồm một số nguyên dương ~N~ ~(1 \leq N \leq 10^5)~. Dòng thứ hai gồm ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ ~(1 \leq A_i \leq 10^9)~.

Output

In ra một số nguyên dương duy nhất là giá trị nhỏ nhất của thể của số dương cuối cùng trong dãy.

Scoring

• Subtask ~1~ (~30~ điểm): ~N = 2~.

• Subtask ~2~ (~70~ điểm): Không có ràng buộc gì thêm.

Sample Input 1

3
2 3 4

Sample Output 1

1

Sample Input 2

2
4 10

Sample Output 2

2

Notes

Một dãy thao tác có thể cho ví dụ 1 là

• ~A_3~ -= ~A_2~, ~A = [2, 3, 1]~

• ~A_2~ -= ~A_1~, ~A = [2, 1, 1]~

• ~A_2~ -= ~A_3~, ~A = [2, 0, 1]~

• ~A_1~ -= ~A_3~, ~A = [1, 0, 1]~

• ~A_1~ -= ~A_3~, ~A = [0, 0, 1]~

Một dãy thao tác có thể cho ví dụ 2 là

• ~A_2~ -= ~A_1~, ~A = [4, 6]~

• ~A_2~ -= ~A_1~, ~A = [4, 2]~

• ~A_1~ -= ~A_2~, ~A = [2, 2]~

• ~A_1~ -= ~A_2~, ~A = [0, 2]~