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.util.*;
import java.io.*;
public class UltimateWeirdnessOfAnArray
{
	public static final int MAX = 200000;
	
	public static void main(String[] args) throws Exception
	{
		FastScanner in = new FastScanner(System.in);
		
		int n = in.nextInt();
		
//		Random rand = new Random();
		
		int[] array = new int[n];
		for(int x = 0; x < n; x++)
		{
			array[x] = in.nextInt();
//			array[x] = rand.nextInt(200000) + 1;
		}
		
		int[] min = new int[MAX + 1];
		Arrays.fill(min, Integer.MAX_VALUE);
		int[] max = new int[MAX + 1];
		boolean[] used = new boolean[MAX + 1];
		int[] init = new int[n + 1];
		for(int y = 0; y < array.length; y++)
		{
			init[y + 1] = init[y];
			
			for(int z = 1; z * z <= array[y]; z++)
			{
				if(array[y] % z == 0)
				{
					min[z] = Math.min(min[z], y);
					max[z] = y;
					
					min[array[y] / z] = Math.min(min[array[y] / z], y);
					max[array[y] / z] = y;
					
					if(used[z])
					{
						init[y + 1] = Math.max(init[y + 1], z);
					}
					
					if(used[array[y] / z])
					{
						init[y + 1] = Math.max(init[y + 1], array[y] / z);
					}
					
					used[z] = true;
					used[array[y] / z] = true;
				}
			}
		}
		
//		System.out.println(Arrays.toString(min));
//		System.out.println(Arrays.toString(max));
		
		ArrayList<Integer>[] intervals = new ArrayList[n];
		for(int a = 0; a < intervals.length; a++)
		{
			intervals[a] = new ArrayList<Integer>();
		}
		
		for(int b = 1; b < min.length; b++)
		{
			if(min[b] < max[b] - 1)
			{
				intervals[max[b]].add(min[b]);
				intervals[max[b]].add(b);
			}
		}
		
//		System.out.println(Arrays.toString(init));
		
		SegmentTree st = new SegmentTree(init);
		
//		System.out.println(Arrays.toString(st.sum));
		
		Arrays.fill(used, false);
		int suffix = 0;
		
		long result = 0;
		for(int b = n - 1; b >= 0; b--)
		{
//			System.out.println("SUM: " + 0 + " " + b);
			
			result += st.query(0, b);
			
//			System.out.println(intervals[b]);
			
			for(int c = 0; c < intervals[b].size(); c += 2)
			{
//				System.out.println("MODIFY: " + (intervals[b].get(c) + 1) + " " + intervals[b].get(c + 1));
				
				st.modify(intervals[b].get(c) + 1, intervals[b].get(c + 1));
			}
			
//			System.out.println("RESULT: " + result);
			
			for(int z = 1; z * z <= array[b]; z++)
			{
				if(array[b] % z == 0)
				{
					min[z] = Math.min(min[z], b);
					max[z] = b;
					
					min[array[b] / z] = Math.min(min[array[b] / z], b);
					max[array[b] / z] = b;
					
					if(used[z])
					{
						suffix = Math.max(suffix, z);
					}
					
					if(used[array[b] / z])
					{
						suffix = Math.max(suffix, array[b] / z);
					}
					
					used[z] = true;
					used[array[b] / z] = true;
				}
			}
			
//			System.out.println(suffix);
			
			st.modify(0, suffix);
		}
		
		System.out.println(result);
	}
	
	static class SegmentTree
	{
		int n;
		long[] sum;
		int[] max;
		int[] min;
		int[] delta;
		
		public SegmentTree(int[] init)
		{
			n = init.length;
			sum = new long[n << 2 | 1];
			max = new int[n << 2 | 1];
			min = new int[n << 2 | 1];
			delta = new int[n << 2 | 1];
			
			build(1, 0, n - 1, init);
		}
		
		public void build(int i, int l, int r, int[] init)
		{
			if(l == r)
			{
				sum[i] = init[l];
				max[i] = init[l];
				min[i] = init[l];
				delta[i] = init[l];
				
//				System.out.println("BUILD: " + i + " " + l + " " + init[l]);
			}
			else
			{
				int mid = (l + r) >> 1;
				build(i << 1, l, mid, init);
				build(i << 1 | 1, mid + 1, r, init);
				update(i);
			}
		}
		
		public void modify(int left, int val)
		{
			modify(1, 0, n - 1, left, val);
		}
		
		public void modify(int i, int l, int r, int left, int val)
		{
			if(r < left || min[i] >= val)
			{
				return;
			}
			else if(l >= left && max[i] < val)
			{
				apply(i, l, r, val);
			}
			else
			{
				prop(i, l, r);
				
				int mid = (l + r) >> 1;
				modify(i << 1, l, mid, left, val);
				modify(i << 1 | 1, mid + 1, r, left, val);
				
				update(i);
			}
		}
		
		public long query(int left, int right)
		{
			return query(1, 0, n - 1, left, right);
		}
		
		public long query(int i, int l, int r, int left, int right)
		{
//			System.out.println("QUERY: " + i + " " + l + " " + r + " " + left + " " + right);
			
			if(r < left || l > right)
			{
				return 0;
			}
			else if(l >= left && r <= right)
			{
//				System.out.println(sum[i]);
				
				return sum[i];
			}
			else
			{
				prop(i, l, r);
				
				int mid = (l + r) >> 1;
				return query(i << 1, l, mid, left, right) + query(i << 1 | 1, mid + 1, r, left, right);
			}
		}
		
		public void apply(int i, int l, int r, int val)
		{
			if(val > delta[i])
			{
				delta[i] = val;
				sum[i] = (long)val * (r - l + 1);
				max[i] = val;
				min[i] = val;
			}
		}
		
		public void prop(int i, int l, int r)
		{
			int mid = (l + r) >> 1;
			apply(i << 1, l, mid, delta[i]);
			apply(i << 1 | 1, mid + 1, r, delta[i]);
		}
		
		public void update(int i)
		{
			sum[i] = sum[i << 1] + sum[i << 1 | 1];
			max[i] = max[i << 1 | 1];
			min[i] = min[i << 1];
		}
	}
	
	static class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream input)
		{
			br = new BufferedReader(new InputStreamReader(input));
			st = new StringTokenizer("");
		}
		
		public String next() throws IOException
		{
			if(st.hasMoreTokens())
			{
				return st.nextToken();
			}
			else
			{
				st = new StringTokenizer(br.readLine());
				return next();
			}
		}
		
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
		}
	}
}
