该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

After winning a silver medal, Snowy enrolled at Peking University. As he strolled happily along a tree-lined path, he recalled a problem he had yet to solve.

Problem Description

Snowy has $n$ candies. The deliciousness of the $i$-th candy is represented by an integer $a_i$.

A lollipop is formed by combining a contiguous sequence of candies. That is, Snowy chooses indices $i$ and $j$ ($1\leq i\leq j\leq n$) and uses all candies from index $i$ to $j$ to make one lollipop.

The deliciousness of a single lollipop is defined as the Least Common Multiple (LCM) of the deliciousness values of all candies contained in it.

Snowy wants to partition all $n$ candies into an arbitrary number of lollipops. Every candy must belong to exactly one lollipop.

Formally, he needs to select partition points $1 \leq r_1 < r_2 < \cdots < r_k = n$ to create $k$ lollipops corresponding to the intervals $[1, r_1], [r_1 + 1, r_2], \cdots, [r_{k-1} + 1, r_k]$.

Find a partition strategy such that the sum of the deliciousness of all lollipops is maximized.

It is guaranteed that the answer will not exceed $10^{18}$.

Input Format

The first line contains a single integer $n$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

Output Format

Output a single integer representing the maximum possible total deliciousness.

Examples

Input 1

3
6 10 15

Output 1

45

Input 2

2
2 3

Output 2

6

Input 3

2
3 6

Output 3

9

Constraints

For $100\%$ of the data, $1 \leq n \leq 2 \times 10^5$ and $1 \leq a_i \leq 10^9$.

This problem has 25 test points divided into 8 subtasks. You must pass all test points in a subtask to receive points for it.

Special Property A: $a_1 = a_2 = \cdots = a_n$.

Special Property B: For any $i$, $a_i$ is either equal to $\operatorname{lcm}(a_1, \dots, a_{i-1})$ or is coprime (gcd is 1) to it.