33837번 - gcd와 set

문제

길이가 $N$인 정수 배열 $A$가 주어진다. 집합 $S = \{1, 2, \dots, N\}$를 정의하자. 집합 $S$의 부분집합 $S'$에 대해, 다음 값의 최댓값을 구하여라.^[1]

$$ \text{gcd}_A(S') + \text{gcd}_A(S \setminus S') $$

집합 $P = \{p_1, p_2, \dots, p_k\}$일 때, $\text{gcd}_A(P)$는 $A_{p_1}, A_{p_2}, \dots, A_{p_k}$의 최대공약수로 정의한다. 만약 집합 $P$가 공집합일 경우에는 $\text{gcd}_A(\varnothing) = 0$으로 정의한다.

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1 \leq N \leq 10^6)$

두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \leq A_i \leq 5\ 000)$

출력

첫 번째 줄에 $\text{gcd}_A(S') + \text{gcd}_A(S \setminus S')$의 최댓값을 출력한다.

제한

노트

[1] $A \setminus B$는 두 집합 $A$와 $B$의 차집합을 나타내는 기호이다.