Daisies and Love

Interview

Time limit1sMemory limit1024 MB

Summary

Find the largest M so that every petal count L_i is congruent to some common value modulo M, where all L_i are multiples of M.

Level: Medium4 of 10
Topics: Math, Number theory, Implementation
Solved: No attempts yet

Problem

An M-state affection list (with $M > 1$ ) is a sequence defined as follows: the first entry is the state “loves”, and the remaining $M-1$ entries are some other (distinct) affection states.

A girl reads a boy's feelings toward her by plucking, one at a time, the petals of a daisy he gives her, using the following rules:

Before the first petal is plucked, we are in the state “loves”.
Each time a petal is plucked, the affection state advances to the next state in the list.
The state that follows the last state in the list is again “loves” (the list wraps around).
When the flower has no petals left, we finish with this daisy and return the current state as its result.

For example, consider the $3$ -state list “loves”-“likes”-“indifferent”. With this list, a daisy of $5$ petals gives the result “indifferent”, while a daisy of $7$ petals gives “likes”.

The girl believes the boy loves her only if he gives her daisies and every one of them points to the state “loves”. The boy wants to convince her, so he gives her $N$ daisies and wants to design the longest possible affection list.

For the given daisies, find the largest value of $M$ for which the girl concludes that the boy loves her.

Input

The first line contains the number of daisies $N$ ( $1 \le N \le 1000$ ). The second line contains $N$ integers $L_i$ ( $1 \le L_i \le 100$ ) separated by spaces, where $L_i$ is the number of petals on the $i$ -th daisy.

Output

Print a single integer: the largest possible value of $M$ . If the petal counts of the daisies share no common divisor greater than $1$ , print $1$ .

Examples5

Example 1
Input
```
4
3 21 12 6
```
Expected output
```
3
```
Example 2
Input
```
1
1
```
Expected output
```
1
```
Example 3
Input
```
1
100
```
Expected output
```
100
```
Example 4
Input
```
2
2 3
```
Expected output
```
1
```
Example 5
Input
```
3
12 18 24
```
Expected output
```
6
```