Trong một vương quốc nọ, nhà vua muốn chia đều số kho báu của mình cho các ngôi làng mà không để lại bất kỳ kho báu dư thừa nào. Nhà vua đã thu thập được 𝑛 hòm vàng, trong đó hòm i chứa một số lượng vàng ~ai (ai<=10^9)~.

Yêu cầu: Nhiệm vụ của bạn là giúp nhà vua tìm số lượng lớn nhất các ngôi làng mà ông có thể chia đều toàn bộ số vàng trong mỗi hòm.

Input

• Dòng ~1~: Ghi số nguyên ~n (n<=10^6)~
• Dòng ~2~: Ghi n số nguyên là số lượng vàng (các số trên ~1~ dòng được ghi cách nhau ~1~ dấu cách)

Output

• Ghi kết quả bài toán

Sample input

4
8 4 2 6

Sample output

2