Сума НСД

Limits: 2 sec., 256 MiB

Задано масив \(a\) з \(n\) елементів. Потрібно розбити його на дві непорожні підмножини \(b\) і \(c\) так, щоб максимізувати НСД(\(b\)) + НСД(\(c\)). Кожен елемент масиву повинен належати рівно одній з підмножин.

НСД масиву — це найбільше ціле число таке, що всі елементу цього масиву діляться на це число.

Input

У першому рядку задано одне ціле число \(n\) — розмір масиву.

У другому рядку задано \(n\) цілих чисел \(a_i\).

Output

У єдиному рядку виведіть одне ціле число — максимальне значення НСД(\(b\)) + НСД(\(c\)).

Constraints

\(2 \le n \le 10^5\),

\(1 \le a_i \le 10^9\).

Samples