Có \(n\) con quái vật, được đánh số từ \(1, 2, ..., n\). Ban đầu, máu của quái vật \(i\) là \(a_i\).

Dưới đây, một con quái vật có ít nhất 1 điểm máu được gọi là còn sống. Cho đến khi chỉ còn lại một con quái vật sống, lặp lại các bước sau:

• Một con quái vật ngẫu nhiên còn sống tấn công một con quái vật ngẫu nhiên khác còn sống.
• Kết quả là máu của con quái vật bị tấn công giảm đi một lượng bằng máu hiện tại của con quái vật tấn công.

Hãy tìm lượng máu cuối cùng nhỏ nhất có thể của con quái vật sống sót cuối cùng.

INPUT FORMAT

Dòng đầu tiên gồm số nguyên dương \(n(1 \leq n \leq 10^5)\).

Dòng thứ hai chứa dãy số \(a\) gồm \(n\) phần tử \((1 \leq a_i \leq 10^9)\).

OUTPUT FORMAT

In ra lượng máu ít nhất có thể của con quái vật cuối cùng.

Ví dụ 1:

Input

4
2 10 8 40

Output

2

Ví dụ 2:

Input

4
5 13 8 1000000000

Output

1

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House