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
// Don't place your source in a package


import javax.swing.*;
import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
import java.util.stream.Stream;



// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

        long Long() {
            return Long.parseLong(next());
        }

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        //reading /writing file
        //Scanner sc=new Scanner(new File("input.txt"));
        //PrintWriter pr=new PrintWriter("output.txt");



        int T=1;
        for(int t=0;t<T;t++){
            //int n=Int();
            //int k=Int();
            int n=Int();
            int A[]=Arr(n);
            Solution sol1=new Solution(out);
            sol1.solution(A);
        }
        out.close();

    }


    public static int[] Arr(int n){
        int A[]=new int[n];
        for(int i=0;i<n;i++)A[i]=Int();
        return A;
    }
    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}








class Solution {
    PrintWriter out;
    int INF = Integer.MAX_VALUE;
    int MOD = 1000000007;
    long mod = 1000000007;

    public Solution(PrintWriter out) {
        this.out = out;
    }


    public void solution(int A[]) {
        int n=A.length;
        long res[]=new long[n];

        TreeSet<Integer>tree=new TreeSet<>();
        for(int i:A)tree.add(i);

        int MAX=300000+10;
        FenWick fen1=new FenWick(300000+10);
        FenWick fen2=new FenWick(300000+10);
        long record[]=new long[MAX];


        fen1.update(A[0],A[0]);
        fen2.update(A[0],1);

        for(int j=A[0];j<MAX;j+=A[0]){
            List<Integer>list=new ArrayList<>();
            Integer hi=tree.higher(j);
            while(hi!=null){
                if(hi>=j+A[0])break;
                list.add(hi);
                hi=tree.higher(hi);
            }
            for(int index:list){
                record[index]+=index-A[0];
            }
        }

        for(int i=1;i<A.length;i++){
            int cur = A[i];
            long sum = res[i-1];
            //less


            long sum1 = fen1.sumRange(0,cur-1);
            sum+=sum1;
            sum+=record[cur];


            for(int j=cur;j<MAX;j+=cur){
                Integer hi=tree.higher(j);
                while(hi!=null){
                    if(hi>=j+cur)break;
                    record[hi]+=(hi-j);
                    hi=tree.higher(hi);
                }

            }

            //large
            long cnt2=fen2.sumRange(cur+1,MAX-1);
            sum+=cnt2*cur;

            if(cur!=1){
                int mul=1;
                for(int j=cur;j<MAX;j+=cur){
                    cnt2=fen2.sumRange(j+1,Math.min(MAX-1,j+cur-1));
                    long sum2=fen1.sumRange(j+1,Math.min(MAX-1,j+cur-1));
                    long sub = cur*mul;
                    sum+=(sum2-(sub*cnt2));
                    mul++;
                }
            }
            res[i]=sum;
            fen1.update(cur,cur);
            fen2.update(cur,1);
        }




        for(long i:res){
            out.print(i+" ");
        }
    }


}


class FenWick {
    long tree[];//1-index based
    public FenWick(int n) {
        tree=new long[n+1];
        int sum=0;
    }

    public void update(int i, int val) {
        i++;
        while(i<tree.length){
            tree[i]+=val;
            i+=(i&-i);
        }
    }

    public long sumRange(int i, int j) {
        return pre(j+1)-pre(i);
    }

    public long pre(int i){
        long sum=0;
        while(i>0){
            sum+=tree[i];
            i-=(i&-i);
        }
        return sum;
    }
}