You have an array a consisting of n distinct positive integers, numbered from 1 to n. Define p_k as $$$p_k = ∑_{1 ≤ i, j ≤ k} a_i mod a_j, where x \bmod y denotes the remainder when x is divided by y. You have to find and print p_1, p_2, \ldots, p_n$$$. 

Input

The first line contains n — the length of the array (2 ≤ n ≤ 2 ⋅ 10^5).

The second line contains n space-separated distinct integers a_1, …, a_n (1 ≤ a_i ≤ 3 ⋅ 10^5, a_i ≠ a_j if i ≠ j). 

Output

Print n integers p_1, p_2, …, p_n. 

Examples

Input


4
6 2 7 3


Output


0 2 12 22


Input


3
3 2 1


Output


0 3 5
/*
stream Butter!
eggyHide eggyVengeance
I need U
xiao rerun when
 */
import static java.lang.Math.*;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;

public class x1553F
{
    static final int MAX = 300000;
    public static void main(String hi[]) throws Exception
    {
        BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(infile.readLine());
        int N = Integer.parseInt(st.nextToken());
        int[] arr = readArr(N, infile, st);
        long[] res = new long[N];
        //i < j
        FenwickTree bit = new FenwickTree(MAX+3);
        long prefix = arr[0];
        bit.add(arr[0], 1);
        for(int i=1; i < N; i++)
        {
            res[i] += prefix;
            long freq = 1L;
            for(int v=arr[i]; v <= MAX; v+=arr[i], freq++)
                res[i] -= freq*bit.find(v, min(MAX, v+arr[i]-1))*arr[i];
            res[i] += res[i-1];
            prefix += arr[i];
            bit.add(arr[i], 1);
        }
        //i > j
        RangeBit contribution = new RangeBit(MAX+3);
        for(int next=arr[0]; next <= MAX; next+=arr[0])
            contribution.add(next, min(MAX, next+arr[0]-1), next);
        long[] res2 = new long[N];
        for(int i=1; i < N; i++)
        {
            long temp = (long)arr[i]*i;
            temp -= contribution.find(arr[i], arr[i]);
            for(int next=arr[i]; next <= MAX; next+=arr[i])
                contribution.add(next, min(MAX, next+arr[i]-1), next);
            res2[i] = res2[i-1]+temp;
            res[i] += res2[i];
        }
        StringBuilder sb = new StringBuilder();
        for(long x: res)
            sb.append(x+" ");
        System.out.println(sb);
    }
    public static int[] readArr(int N, BufferedReader infile, StringTokenizer st) throws Exception
    {
        int[] arr = new int[N];
        st = new StringTokenizer(infile.readLine());
        for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        return arr;
    }
}
class FenwickTree
{
    //Binary Indexed Tree
    //1 indexed
    public int[] tree;
    public int size;

    public FenwickTree(int size)
    {
        this.size = size;
        tree = new int[size+5];
    }
    public void add(int i, int v)
    {
        while(i <= size)
        {
            tree[i] += v;
            i += i&-i;
        }
    }
    public int find(int i)
    {
        int res = 0;
        while(i >= 1)
        {
            res += tree[i];
            i -= i&-i;
        }
        return res;
    }
    public int find(int l, int r)
    {
        return find(r)-find(l-1);
    }
}
class RangeBit
{
    //FenwickTree and RangeBit are faster than LazySegTree by constant factor
    final long[] value;
    final long[] weightedVal;

    public RangeBit(int treeTo)
    {
        value = new long[treeTo+2];
        weightedVal = new long[treeTo+2];
    }
    private void updateHelper(int index, long delta)
    {
        long weightedDelta = index*delta;
        for(int j = index; j < value.length; j += j & -j)
        {
            value[j] += delta;
            weightedVal[j] += weightedDelta;
        }
    }
    public void add(int from, int to, int delta)
    {
        updateHelper(from, delta);
        updateHelper(to + 1, -delta);
    }
    private long query(int to)
    {
        long res = 0;
        long weightedRes = 0;
        for (int j = to; j > 0; j -= j & -j)
        {
            res += value[j];
            weightedRes += weightedVal[j];
        }
        return ((to + 1)*res)-weightedRes;
    }
    public long find(int from, int to)
    {
        if (to < from)
            return 0;
        return query(to) - query(from - 1);
    }
}