시철이가 사랑한 GCD

시철이는 신촌에서 가장 아름다운 자취방을 구하려 한다. 너무 바빠서 직접 방을 보러 다닐 수 없었던 시철이는 인터넷에 올라온 매물번호와 최대공약수(GCD)를 이용해 자취방의 아름다움을 예측하려 한다. 아름다움을 계산하는 방법은 다음과 같다.

1. 매물번호를 나타내는 정수 배열 $S$가 있다. ($|S| = N$, $|S|$는 $S$의 원소 개수)
2. 배열 $S$의 원소를 왼쪽부터 $\lfloor \frac{|S|}{2} \rfloor$개 선택하거나, 오른쪽부터 $\lceil \frac{|S|}{2} \rceil$개 선택한다. 만약 $S$의 원소가 단 한 개라면 그 원소를 선택한다.
3. 선택한 원소들의 $GCD$를 구한다.
4. 선택하지 않은 원소들로 이루어진 배열 $S'$에 대해 2번부터 다시 반복한다.
5. 자취방의 아름다움은 3번에서 구한 $GCD$들의 합의 최댓값으로 정의한다.

매물번호를 이용해 자취방의 아름다움을 계산해 보자!

첫째 줄에 정수 $N$이 주어진다. ($1 \leq N \leq 200\,000$)

둘째 줄에 자취방의 매물번호를 의미하는 정수 $a_1, a_2, \cdots, a_N$이 주어진다. ($1 \leq a_i \leq 200\,000$)

자취방의 아름다움을 출력한다.