Sample Size

While reading the results of a poll in a newspaper article, you might notice that all of the reported percentages are 25%, 50%, and 75% — which makes you suspect that perhaps only 4 people were interviewed, so the poll may not be very reliable.

In this problem you perform a similar analysis. Given the percentages that appear in a newspaper article, determine the minimum number of people that must have been interviewed so that all of those percentages are possible. Percentages are rounded to the nearest integer, with .5 rounded up. For example, 1 out of 3 people is 33%, 2 out of 3 people is 67%, and 155 out of 1000 people is 16%.

Formally, a percentage is achievable with $N$ interviewees if there is an integer $k$ with $0 \le k \le N$ such that rounding $\dfrac{100k}{N}$ gives that percentage. Output the smallest $N$ for which every percentage in the input is achievable.

The first line contains an integer $M$, the number of percentages that appear in the article. ($1 \le M \le 100000$)

Each of the following $M$ lines contains one integer percentage $P$. ($0 \le P \le 100$)

Output the minimum number of people $N \ge 1$ that must be interviewed so that every percentage in the input can be written as the rounded fraction of some number of those people.