Number theory is interesting, while this problem is boring.
Here is the problem. Given an integer sequence a
1, a
2, …, a
n, let S(i) = {j|1<=j<i, and a
j is a multiple of a
i}. If S(i) is not empty, let f(i) be the maximum integer in S(i); otherwise, f(i) = i. Now we define b i as a
f(i). Similarly, let T(i) = {j|i<j<=n, and a
j is a multiple of a
i}. If T(i) is not empty, let g(i) be the minimum integer in T(i); otherwise, g(i) = i. Now we define c
i as a
g(i). The boring sum of this sequence is defined as b
1 * c
1 + b
2 * c
2 + … + b
n * c
n.
Given an integer sequence, your task is to calculate its boring sum.
The input contains multiple test cases.
Each case consists of two lines. The first line contains an integer n (1<=n<=100000). The second line contains n integers a
1, a
2, …, a
n (1<= a
i<=100000).
The input is terminated by n = 0.
Output the answer in a line.