21870번 - 시철이가 사랑한 GCD 출처

Q1. 사막에서 바늘을 찾는 방법은?

A1. 대학원생을 시킨다.

Q2. 신촌에서 자취방을 구하는 방법은?

A2. 대학원생을 시킨다.

연희동 최고의 대학원생 시철이는 오늘도 바쁘다. 그런 시철이도 이번 주말만큼은 꼭 해야 하는 일이 있었는데, 바로 자취방을 구하는 일이다!

시철이는 신촌에서 가장 아름다운 자취방을 구하고 싶다. 하지만 시철이는 매우 바빴기 때문에 직접 방을 찾아다닐 수 없었다. 그래서 시철이는 인터넷에서 본 매물번호와 $GCD$(Greatest Common Divisor, 최대공약수)를 이용해 자취방의 아름다움을 예측하려 했다. 아름다움을 측정하는 자세한 방법은 다음과 같다.

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$)

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