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]~
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
THÊM CÁI SPOILER VÀO
This comment is hidden due to too much negative feedback. Show it anyway.