John Doe offered his sister Jane Doe find the gcd of some set of numbers a.

Gcd is a positive integer g, such that all number from the set are evenly divisible by g and there isn't such g' (g' > g), that all numbers of the set are evenly divisible by g'.

Unfortunately Jane couldn't cope with the task and John offered her to find the ghd of the same subset of numbers.

Ghd is a positive integer g, such that at least half of numbers from the set are evenly divisible by g and there isn't such g' (g' > g) that at least half of the numbers from the set are evenly divisible by g'.

Jane coped with the task for two hours. Please try it, too.

Input

The first line contains an integer n (1 ≤ n ≤ 106) showing how many numbers are in set a. The second line contains space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 1012). Please note, that given set can contain equal numbers.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the %I64d specifier.

Output

Print a single integer g — the Ghd of set a.

Examples

Input

6
6 2 3 4 5 6


Output

3


Input

5
5 5 6 10 15


Output

5
1
1
 1
7
 2
1 7
 100
32 40 7 3 7560 21 7560 7560 10 12 3 7560 7560 7560 7560 5 7560 7560 6 7560 7560 7560 35 7560 18 7560 7560 7560 7560 7560 48 2 7 25 7560 2 2 49 7560 7560 15 16 7560 7560 2 7560 27 7560 7560 7560 7560 3 5 7560 8 7560 42 45 5 7560 5 7560 4 7 3 7560 7 3 7560 7 2 7560 7560 5 3 7560 7560 28 7560 7560 14 7560 5 7560 20 7560 24 7560 2 9 36 7 7560 7560 7560 7560 7560 30 7560 50
 1
3

1
 7
 7
 7560
 3

#pragma GCC optimize("Ofast,vpt,unroll-loops,shrink-wrap-separate,loop-nest-optimize")
 
#include <bits/stdc++.h>
// #include <tr1/unordered_map>
// #include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define mt make_tuple
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define mat vector<vector<ll>>
#define mat2 vector<vector<mat>>
#define vi vector<int>
#define vll vector<ll>
#define lll __int128_t
#define psi pair<string, int>
#define pis pair<int, string>
#define pic pair<int, char>
#define pcc pair<char, char>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define piiii pair<pii, pii>
#define mii map<int, int>
#define umii tr1::unordered_map<int, int>
#define iter vector<piiii>::iterator
#define lb lower_bound
#define ub upper_bound
 
 
#define fi first
#define se second

/*
#define fi first.first
#define se first.second
#define th second.first
#define fo second.second
*/

/*
#define piii pair<int, pii>
#define fi first
#define se second.fi
#define th second.second
*/
 
/*
#define piii pair<pii, int>
#define fi first.first
#define se first.th
#define th second
*/
 
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
using namespace std;
// using namespace __gnu_cxx;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;
 
const int nax = 1000005, lgax = 24, bit = 31, mod = 1000000007, inf = 1000000007;
const ll llax = 1e18;
// const ld pi = 3.14159265358979323846, eps = 1e-7;
 
mt19937 rnd(102372871);
/*
inline int read() {
	char c = getchar_unlocked();
	int t = 0, f = 1;
	while ((c < '0' || '9' < c) && c != EOF)
		f = (c == '-' ? -1 : 1), c = getchar_unlocked();
	while (('0' <= c && c <= '9') && c != EOF)
		t = t * 10 + c - '0', c = getchar_unlocked();
	return t * f;
}

inline void read(char* s) {
	char c = getchar_unlocked();
	while (!isalpha(c))
		c = getchar_unlocked();
	while (isalpha(c))
		*s++ = c, c = getchar_unlocked();
	*s = '\0';
}
*/

struct chash {
	static uint64_t splitmix64(uint64_t x)
	{
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	size_t operator()(uint64_t x) const
	{
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};


ll a[nax];
int n;
gp_hash_table<ll, int, chash> d;

inline bool check(ll x) {
	int cnt = 0;
	for (pair<ll, int> p : d)
		cnt += p.fi % x == 0 ? p.se : 0;
	return cnt >= ((n + 1) >> 1);
}

int main() {
	IOS
	ll ans = 1;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int k = 0; k < 4; ++k) {
		int i = rnd() % n;
		d.clear();
		for (int j = 0; j < n; ++j)
			++d[gcd(a[i], a[j])];
		for (pair<ll, int> p : d)
			if (check(p.fi))
				ans = max(ans, p.fi);
	}
	cout << ans << '\n';
	return 0;
}

