Hardik and his girlfriend, both love to play with numbers. They both used to talk with each other by sending some numbers as messages. His girlfriend sent him a message containing N Integers. Now he wants to reply her.
He is lazy AF! He doesn't want to type a new message . But he can't directly copy the message and send her back the same message. He decided to remove any one Integer from all N Integers.
Now he has N choices to delete a single integer. He prefers to delete an element after deletion of which GCD of the remaining elements is as maximum as possible.
He wants you to find the maximum possible GCD he can get after deleting exactly one element from N integers.
GCD is Greatest Common Divisior.
Input Format:
First line contains a single Integer N, Total number of elements.
Second line contains N space separated Integers A[i]s.
Output Format:
Print the only single integer indication maximum possible GCD after deleting exactly one element.
Constraints:
2<=N<=10^6
1<=A[i]<=10^9
If we delete first element, GCD of remaining elements = GCD(3,4)=1.
If we delete second element, GCD=> GCD(2,4)=2.
If we delete third element, GCD=> GCD(2,3)=1.
Maximum GCD among all these possible GCDs is 2 so answer is 2.
