# Ghd

## 题意翻译

另一个集合s的ghd为max{gcd（s'）||s'|>=0.5|s|} 给定序列a，求ghd

## 题目描述

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.

## 输入输出格式

### 输入格式

The first line contains an integer $ n $ ( $ 1<=n<=10^{6} $ ) showing how many numbers are in set $ a $ . The second line contains space-separated integers $ a_{1},a_{2},...,a_{n} $ $ (1<=a_{i}<=10^{12}) $ . 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.

### 输出格式

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

## 输入输出样例

### 输入样例 #1

```
6
6 2 3 4 5 6
```

### 输出样例 #1

```
3
```

### 输入样例 #2

```
5
5 5 6 10 15
```

### 输出样例 #2

```
5
```