Thành phố Z đã phát triển kinh tế vượt trội trong những năm gần đây, khiến cho hầu hết người dân ở thành phố này trở nên giàu có. kieuphat159 là một cảnh sát giao thông trực thuộc thành phố Z. Vì sự giàu có của người dân, các mức phí phạt khi vi phạm giao thông giờ đây không còn là vấn đề với họ, dẫn đến việc vi phạm giao thông trong thành phố này ngày một nhiều.

Vì sự an toàn giao thông của thành phố, kieuphat159 quyết định sẽ bổ sung một số mức phạt mỗi khi vi phạm. Cụ thể, ngoài mức phí phạt phải đóng, người vi phạm còn phải giải bài toán sau: Người vi phạm sẽ được nhận một dãy gồm ~n~ số nguyên dương. Nhiệm vụ của họ là tìm một số bán bội lớn nhất của dãy này. Số bán bội của dãy là số thỏa mãn có ít nhất ~\frac{n}{2}~ phần tử của dãy là bội của nó.

Với sự giàu có của mình, người vi phạm đã thuê bạn giúp họ giải quyết bài toán này, hãy viết chương trình tìm số bán bội lớn nhất ấy.

Dữ liệu

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10 ^ 6)~
• Dòng tiếp theo chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^{12})~

Kết quả

• Một số nguyên duy nhất là số bán bội lớn nhất tìm được.

Giới hạn

• Subtask ~1~ ~(15\%)~: ~n \le 10^4, a_i \le 10^4~
• Subtask ~2~ ~(40\%)~: ~n \le 10^4, a_i \le 10^{12}~
• Subtask ~3~ ~(45\%)~: không có ràng buộc nào thêm

Ví dụ 1

Dữ liệu

3
1 2 3

Kết quả

1

Ví dụ 2

Dữ liệu

8
6 4 4 5 3 3 5 9

Kết quả

3