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

import static java.lang.System.currentTimeMillis;

import java.io.*;
import java.util.*;

public class D {

	static void solve() throws IOException {
		// long time = System.currentTimeMillis();
		long timeLimit = System.currentTimeMillis() + 3300;
		Random rng = new Random(58 + 50216);
		int n = (int) nextLong();
		long[] a = new long[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextLong();
		}
		long answer = 1;
		while (System.currentTimeMillis() < timeLimit) {
			int index = rng.nextInt(n);
			long best = checkDivisorsOf(a, a[index]);
			answer = Math.max(answer, best);
		}
		out.println(answer);
		// System.err.println(System.currentTimeMillis() - time);
	}

	static class MyLong {
		long value;

		@Override
		public int hashCode() {
			return (int) ((value * 50215) ^ (value >>> 32));
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			MyLong other = (MyLong) obj;
			if (value != other.value)
				return false;
			return true;
		}
	}

	static MyLong[] temporary = new MyLong[10000];
	static {
		for (int i = 0; i < temporary.length; i++) {
			temporary[i] = new MyLong();
		}
	}

	static int[] countForId = new int[10000];
	static Map<MyLong, Integer> map = new HashMap<MyLong, Integer>(10000);

	private static long checkDivisorsOf(long[] a, long value) {
		map.clear();
		long time = currentTimeMillis();
		for (long i : a) {
			long gcd = binaryGCD(i, value);
			MyLong myLong = temporary[map.size()];
			myLong.value = gcd;
			Integer id = map.get(myLong);
			if (id == null) {
				countForId[map.size()] = 0;
				id = map.size();
				map.put(myLong, id);
			}
			countForId[id]++;
		}
		time = currentTimeMillis() - time;
		// System.err.println("time: "+time);
		// System.err.println(map.size());
		long[] divisor = new long[map.size()];
		int[] count = new int[map.size()];
		int cnt = 0;
		for (Map.Entry<MyLong, Integer> entry : map.entrySet()) {
			divisor[cnt] = entry.getKey().value;
			count[cnt] = countForId[entry.getValue()];
			++cnt;
		}
		int[] newCount = new int[map.size()];
		for (int i = 0; i < cnt; i++) {
			for (int j = 0; j < cnt; j++) {
				if (divisor[j] % divisor[i] == 0) {
					newCount[i] += count[j];
				}
			}
		}
		long best = 1;
		int want = (a.length + 1) >> 1;
		for (int i = 0; i < cnt; i++) {
			if (newCount[i] >= want) {
				best = Math.max(best, divisor[i]);
			}
		}
		return best;
	}

	static long gcd(long a, long b) {
		while (a > 0 && b > 0) {
			if (a < Integer.MAX_VALUE && b < Integer.MAX_VALUE) {
				return intGCD((int) a, (int) b);
			}
			if (a > b) {
				a %= b;
			} else {
				b %= a;
			}
		}
		return a | b;
	}

	private static long intGCD(int a, int b) {
		while (a > 0 && b > 0) {
			if (a > b) {
				a %= b;
			} else {
				b %= a;
			}
		}
		return a | b;
	}

	static long binaryGCD(long x, long y) {
		if (x == 0)
			return y;

		if (y == 0)
			return x;

		long cf2 = Long.numberOfTrailingZeros(x | y);

		x >>= Long.numberOfTrailingZeros(x);

		for (;;) {
			y >>= Long.numberOfTrailingZeros(y);

			if (x == y)
				break;

			if (x > y) {
				long t = x;
				x = y;
				y = t;
			}
			if (x == 1)
				break;

			y -= x;
		}

		return x << cf2;
	}

	static BufferedReader br;
	static PrintWriter out;

	public static void main(String[] args) throws IOException {
		InputStream input = System.in;
		PrintStream output = System.out;
		File file = new File("d.in");
		if (file.exists() && file.canRead()) {
			input = new FileInputStream(file);
		}
		br = new BufferedReader(new InputStreamReader(input));
		out = new PrintWriter(output);
		solve();
		out.close();
	}

	public static long nextLong() throws IOException {
		int c = br.read();
		while ((c < '0' || c > '9') && c != '-')
			c = br.read();
		boolean negative = false;
		if (c == '-') {
			negative = true;
			c = br.read();
		}
		long m = 0;
		while (c >= '0' && c <= '9') {
			m = m * 10 + c - '0';
			c = br.read();
		}
		return negative ? -m : m;
	}
}
