Boring Sum

Number theory is interesting, while this problem is boring.

Here is the problem. Given an integer sequence a₁, a₂, …, 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 bi 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₁ * c₁ + b₂ * c₂ + … + 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₁, a₂, …, a_n (1<= a_i<=100000).

The input is terminated by n = 0.

Output the answer in a line.

5
1 4 2 3 9
0

136

In the sample, b1=1, c1=4, b2=4, c2=4, b3=4, c3=2, b4=3, c4=9, b5=9, c5=9, so b1 * c1 + b2 * c2 + … + b5 * c5 = 136.

SYSU

2014 Multi-University Training Contest 9