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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define sz size()
#define SZ(x) int(x.size())
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define quix ios_base::sync_with_stdio(0);cin.tie(0);
#define binary(n, len) cout << bitset<len>(n) << '\n'
#define rr read
#define ww write
#define ha puts("YES")
#define na puts("NO")
#ifndef ONLINE_JUDGE 
#include "/home/asif/Codes/Library/debug.h"
#endif

//IO

template<typename T>
inline void read(T& t){
  t = 0; char f = 0, ch = getchar();
  double d = 0.1;
  while(ch > '9' or ch < '0') f |= (ch == '-'), ch = getchar();
  while(ch <='9' and ch >= '0') t = t * 10 + ch - 48,ch = getchar();
  if(ch == '.') {
    ch = getchar();
    while(ch <= '9' && ch >= '0') t += d * (ch^48), d *= 0.1, ch = getchar();
  }
  t = ( f ? -t : t);
}
template<typename T, typename... Args>
inline void read(T& t, Args&... args){ read(t); read(args...);}

template<typename T>
void write(T t){ cout << t << '\n'; }
template <typename T, typename... Args>
void write(T t, Args... args) {
  cout << t << ' '; write(args...);
}

template<typename T>
void write(std::vector<T> &v){
  for(int i = 0; i < v.sz; i++)cout << v[i] << " \n" [i == SZ(v) - 1];
}

// Characters and Strings

bool isLetter(char c) { return (c >= 'A' and c <= 'Z') or (c >= 'a' and c <= 'Z');}
bool isUpperCase(char c){ return c >= 'A' and c <= 'Z'; }
bool isLowerCase(char c){ return c >= 'a' and c <= 'z';}
bool isDigit(char c){ return c >= '0' and c <= '9'; }
bool isVowel(char c){ return c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'; }
bool isConsonant(char c){ return !isVowel(c); }

template<class T> 
string toString(T n){
  ostringstream ost;
  ost << n; ost.flush();
  return ost.str();
}

// Bit Hacks

ll setBit(ll mask, int p){ return (mask | (1 << p)); }
ll resetBit(ll mask, int p){ return (mask & ~(1 << p)); }
ll flipBit(ll mask, int p){ return (mask ^ (1 << p)); }
bool check(ll mask, int p){ return (mask & (1 << p)); }

int msb(long long N){ return N ? 63 - __builtin_clzll(N): -1; }
int lsb(long long N){ return __builtin_ffs(N) - 1;}
int countOn(ll mask){ return __builtin_popcountll(mask); }
int countOff(ll mask){ return msb(mask) - countOn(mask) + 1; }

// Math

ll nC2(ll n) { return (n * (n - 1)) / 2; }
ll nc3(ll n) { return (n * (n - 1) * (n - 2)) / 6; }

ll apsum(ll n, ll a = 1, ll d = 1){ return (n * (a + a + (n - 1) * d) ) / 2; }

ll lcm(ll a, ll b){ return (a / __gcd(a, b) ) * b; }

ll sqr(ll n){ return n * n; }
ll cub(ll n){ return n * n * n; }

template<typename A, typename P>
int bigMod(A a, P p, const int MOD){
  int ret = 1;
  while(p){
    if(p & 1)ret = (1LL * ret * a) % MOD;
    a = (1LL * a * a) % MOD;
    p >>= 1LL;
  }
  return ret;
}

template<typename T>
T toBase(T n, T base){
  T ret = 0LL;
  while(n){
    ret += n % base;
    ret *= 10LL;
    n /= base;
  }
  return ret;
}

template<class T> struct Fraction{T a, b; Fraction(T a = 0,T b = 1); string toString();};
template<class T> Fraction<T>::Fraction(T a,T b){T d=__gcd(a,b);a/=d;b/=d;if (b<0) a=-a,b=-b;this->a=a;this->b=b;}
template<class T> string Fraction<T>::toString(){ostringstream sout;sout<<a<<" / "<<b;return sout.str();}
template<class T> Fraction<T> operator+(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b+q.a*p.b,p.b*q.b);}
template<class T> Fraction<T> operator-(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b-q.a*p.b,p.b*q.b);}
template<class T> Fraction<T> operator*(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.a,p.b*q.b);}
template<class T> Fraction<T> operator/(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b,p.b*q.a);}

// Misc

ll rand(ll l, ll r) { //[l, r]
  #ifdef LOCAL
  static mt19937_64 gen;
  #else
  static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  #endif
  return uniform_int_distribution<ll>(l, r)(gen);
}

template<typename T>
ll sumv(std::vector<T> &v){ return std::accumulate(all(v), 0); }

template<typename T>
T minv(std::vector<T> &v){ return *std::min_element(all(v)); }

template<typename T>
T maxv(std::vector<T> &v){ return *std::max_element(all(v)); }

template<typename T>
void make_unique(std::vector<T> &v){ sort(all(v)); v.resize(unique(all(v)) - v.begin()); }

template<typename T>
int lowerBound(std::vector<T> &v, T x){ return v.back() < x ? -1 : lower_bound(all(v), x) - v.begin(); }

template<typename T>
int upperBound(std::vector<T> &v, T x){ return v.back() < x ? -1 : upper_bound(all(v), x) - v.begin(); }

double startTime = clock();
void showCurrentTime() { printf("%.6lf\n", ((double)clock() - startTime) / CLOCKS_PER_SEC); }

/*-------------------------------------------------------------------------------------------------------*/

const double EPS = 1e-9;
const double PI = acos(-1.0);
const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
const int dx[] = {1, -1, 0, 0, -1, -1, 1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1, -1, 1};

/*-------------------------------------------------------------------------------------------------------*/

int main() {
  
  int n;
  rr(n);
  std::vector<ll> v(n), d(n);
  for(auto &x : v) rr(x);

  int trial = 10;
  ll ans = 0;
  while(trial--){
    int idx = rand(0, n - 1);
    map<ll, ll> cnt;
    for(int i = 0; i < n; i++) {
      ll d = __gcd(v[idx], v[i]);
      cnt[d]++;
    }
    std::vector<pair<ll, ll> > w;
    for(auto x : cnt) w.eb(x.ff, x.ss);
    for(int i = 0; i < w.sz; i++){
      int tot = w[i].ss;
      for(int j = i + 1; j < w.sz; j++){
        if(w[j].ff % w[i].ff) continue;
        tot += w[j].ss;
      }
      if(tot >= n - tot) ans = max(ans, w[i].ff);
    }
  }
  printf("%lld\n", ans);
  return 0;
}