Maximum GCD

Time limit1sMemory limit1024 MB

Summary

Given an array of up to 1e5 positive integers, find the largest d such that repeated modulo operations (never producing 0) can make every element a multiple of d.

Level: Medium5 of 10
Topics: Math, Number theory, Array
Solved: No attempts yet

Problem

Grammy has an array of length $n$ . She recently learned about the concept of greatest common divisor (GCD). The GCD of an array is the maximum integer $d$ such that every element in the array is divisible by $d$ . Grammy wants the GCD to be as large as possible so that the array is beautiful.

You want to help Grammy make her array beautiful. You may perform zero or more modulo operations on each element. In one operation, you choose an element $a_i$ ( $1 \leq i \leq n$ ) and another integer $x$ , then replace $a_i$ with $a_i \bmod x$ . Grammy does not want 0 in her array, so you cannot change $a_i$ into 0 with a modulo operation.

Find the maximum GCD of the array after any number of modulo operations.

Input

The first line contains a single integer $n$ ( $1 \leq n \leq 10^5$ ), the number of elements in the array.

The second line contains $n$ positive integers $a_i$ ( $1 \leq a_i \leq 10^9$ ), the initial elements of the array.

Output

Output a single integer, the maximum GCD of the array after any number of modulo operations.

Examples1

Example 1
Input
```
3
3 10 7
```
Expected output
```
3
```