Sample Size

Time limit2sMemory limit512 MB

Summary

Given a set of rounded percentages, find the smallest number of interviewees N such that each percentage equals 100k/N rounded to the nearest integer.

Level: Medium6 of 10
Topics: Math, Number theory, Binary search, Brute force
Solved: No attempts yet

Problem

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.

Input

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

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.

Examples2

Example 1
Input
```
3
25
50
75
```
Expected output
```
4
```
Example 2
Input
```
2
33
67
```
Expected output
```
3
```