Yasin has an array a containing n integers. Yasin is a 5 year old, so he loves ultimate weird things.

Yasin denotes weirdness of an array as maximum gcd(ai, aj) value among all 1 ≤ i < j ≤ n. For n ≤ 1 weirdness is equal to 0, gcd(x, y) is the greatest common divisor of integers x and y.

He also defines the ultimate weirdness of an array. Ultimate weirdness is <image> where f(i, j) is weirdness of the new array a obtained by removing all elements between i and j inclusive, so new array is [a1... ai - 1, aj + 1... an].

Since 5 year old boys can't code, Yasin asks for your help to find the value of ultimate weirdness of the given array a!

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of elements in a.

The next line contains n integers ai (1 ≤ ai ≤ 200 000), where the i-th number is equal to the i-th element of the array a. It is guaranteed that all ai are distinct.

Output

Print a single line containing the value of ultimate weirdness of the array a. 

Example

Input

3
2 6 3


Output

6

Note

Consider the first sample.

  * f(1, 1) is equal to 3. 
  * f(2, 2) is equal to 1. 
  * f(3, 3) is equal to 2. 
  * f(1, 2), f(1, 3) and f(2, 3) are equal to 0. 

Thus the answer is 3 + 0 + 0 + 1 + 0 + 2 = 6.
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.*;
public class Main {

	public static void main(String[] args) throws FileNotFoundException {
		
		new TaskC().solve();
	}

}

class TaskC {
	int n;
	int[] a;
	long[] count;
	int mx;
	ArrayList<Integer>[] where, fwhere;
	
	void solve() throws FileNotFoundException {
		Scanner in = new Scanner(System.in);
//		Scanner in = new Scanner(new FileInputStream("cf_java.txt"));
		
		n = in.nextInt();
		a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = in.nextInt();
		
		mx = 0;
		for (int i = 0; i < n; i++)
			mx = Math.max(a[i],  mx);
		
		where = new ArrayList[mx + 1];
		fwhere = new ArrayList[mx + 1];
		
		for (int i = 0; i <= mx; i++) {
			where[i] = new ArrayList<Integer>();
			fwhere[i] = new ArrayList<Integer>();
		}
		
		for (int i = 0; i < n; i++)
			where[a[i]].add(i);
		
		for (int i = 1; i <= mx; i++) {
			for (int j = i; j <= mx; j += i)
				fwhere[i].addAll(where[j]);
		}
		
		for (int i = 1; i <= mx; i++)
			Collections.sort(fwhere[i]);
		
	
		Seg root = new Seg(0, n);
		count = new long[mx + 1];
		for (int gcd = mx; gcd >= 0; gcd--) {
			
			count[gcd] = 1L * n * n - root.sum;
			if (fwhere[gcd].size() < 2)
				continue;
			
			//..o..o..o..
			int b1 = fwhere[gcd].get(0);
			int b2 = fwhere[gcd].get(1);
			int b3 = fwhere[gcd].get(fwhere[gcd].size() - 2);
			int b4 = fwhere[gcd].get(fwhere[gcd].size() - 1);
			if (0 < b1 + 1)
				root.updateMx(0, b1 + 1, b3);
			if (b1 + 1 < b2 + 1)
				root.updateMx(b1 + 1, b2 + 1, b4);
			if (b2 + 1 < n)
				root.updateMx(b2 + 1, n, n);
			
		}
		
		long ans = 0;
		for (int gcd = 1; gcd <= mx; gcd++) 
			ans += (count[gcd] - count[gcd-1]) * gcd;
		
		System.out.println(ans);
	}
}

class Seg {
	int l, r, mn, mx, same; // [l, r)
	long sum;
	Seg[] ch;
	Seg(int l, int r) {
		this.l = l;
		this.r = r;
		this.same = -1;
		ch = new Seg[2];
		
		if (l + 1 == r) {
			this.sum = this.mn = this.mx = l;
			return;
		}
		
		int m = (l + r) / 2;
		ch[0] = new Seg(l, m);
		ch[1] = new Seg(m, r);
		
		pushUp();
	}
	void pushUp() {
		this.sum = ch[0].sum + ch[1].sum;
		this.mn = Math.min(ch[0].mn, ch[1].mn);
		this.mx = Math.max(ch[0].mx, ch[1].mx);
	}
	void makeSame(int v) {
		mn = mx = v;
		sum = 1L * (r - l) * v;
		same = v;
	}
	void pushDown() {
		if (l + 1 != r && same != -1) {
			ch[0].makeSame(same);
			ch[1].makeSame(same);
			same = -1;
		}
	}
	void updateMx(int l, int r, int mx) {
		if (l <= this.l && this.r <= r && this.mx <= mx) {
			makeSame(mx);
			return;
		}
		
		pushDown();
		int m = (this.l + this.r) / 2;
		
		//[l, r) && [this.l, m)
		if (l < m && this.l < r && ch[0].mn < mx)
			ch[0].updateMx(l, r, mx);
		
		//[l, r) && [m, this.r)
		if (m < r && l < this.r && ch[1].mn < mx)
			ch[1].updateMx(l, r, mx);
		
		pushUp();
	}
}

