A. Prefix GCD
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of length $$$n$$$, perform the following operation exactly once:

— Delete an element from the array, then concatenate the resulting parts (i.e., if you remove the $$$i$$$-th element, the array becomes $$$a_1, a_2, \dots, a_{i - 1}, a_{i + 1}, \dots, a_n$$$).

Let $$$b_1, b_2, \dots, b_{n - 1}$$$ be the resulting array after performing the above operation exactly once on the array $$$a$$$.

Find the maximum possible sum of the values of GCD of each prefix in the array $$$b$$$.

More formally, find the maximum value of: $$$$$$\sum_{i = 1}^{n - 1} gcd(b_1, b_2, \dots, b_i)$$$$$$

Over all the arrays $$$b$$$ resulting from applying the mentioned operation on the array $$$a$$$ exactly once.

Note: $$$gcd(x_1, x_2, \dots, x_k)$$$ is the greatest integer that divides all the values $$$x_1, x_2, \dots, x_k$$$ evenly without a remainder.

Input

The first line of the input contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the size of the array.

The second line of the input consists of $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Output

Output a single integer — the answer to the problem.

Examples
Input
4
4 3 2 1
Output
7
Input
3
18 3 9
Output
27
Input
3
100 100 100
Output
200