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
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String args[]) {new Main().run();}

    FastReader in = new FastReader();
    PrintWriter out = new PrintWriter(System.out);
    void run() {
        work();
        out.flush();
    }
    long mod=1000000007;
    long gcd(long a,long b) {
        return a==0?b:gcd(b%a,a);
    }
    int maxn=300005;
    long[] sum;
    long[] lazy;
    int n;
    void work() {
        n=ni();
        int[] A=nia(n);
        sum=new long[maxn<<2];
        lazy=new long[maxn<<2];
        long[] S=new long[maxn];
        long[] count=new long[maxn];
        long[] ret=new long[n];
        for(int i=0;i<n;i++){
            for(int j=0;j*A[i]<maxn;j++){
                int s=A[i]*j,e=Math.min(A[i]*(j+1)-1,maxn-1);
                long v=query(s,e,S);
                long c=query(s,e,count);
                ret[i]+=v-c*A[i]*j;
            }
            add(A[i],A[i],S);
            add(A[i],1,count);
        }
        for(int i=0;i<n;i++){
            ret[i]+=i*A[i]-query(1,A[i],A[i],0,maxn);
            for(int j=0;j*A[i]<maxn;j++){
                int s=A[i]*j,e=Math.min(A[i]*(j+1)-1,maxn-1);
                add(1,s,e,A[i]*j,0,maxn);
            }
        }
        for(int i=1;i<n;i++){
            ret[i]+=ret[i-1];
        }
        for(long r:ret){
            out.print(r+" ");
        }
    }

    private long query(int node,int s, int e, int l, int r) {
        int m=(l+r)/2;
        push(node,l,r);
        if(s<=l&&r<=e){
            return sum[node];
        }
        long ret=0;
        if(s<=m){
            ret+=query(node<<1,s,e,l,m);
        }
        if(e>=m+1){
            ret+=query(node<<1|1,s,e,m+1,r);
        }
        return ret;
    }

    private void push(int node, int l, int r) {
        sum[node]+=lazy[node]*(r-l+1);
        if(l!=r){
            lazy[node<<1]+=lazy[node];
            lazy[node<<1|1]+=lazy[node];
        }
        lazy[node]=0;
    }

    private void add(int node,int s, int e, long v, int l, int r) {
        if(s<=l&&r<=e){
            lazy[node]+=v;
            return;
        }
        sum[node]+=(Math.min(r,e)-Math.max(s,l)+1)*v;
        int m=(l+r)/2;
        if(s<=m){
            add(node<<1,s,e,v,l,m);
        }
        if(e>=m+1){
            add(node<<1|1,s,e,v,m+1,r);
        }
    }

    int lowbit(int f){
        return f&-f;
    }

    long query(int s,int e,long[] B){
        return query(e,B)-query(s-1,B);
    }

    long query(int idx,long[] B){
        int n=B.length;
        long ret=0;
        for(;idx>0;idx-=lowbit(idx)){
            ret+=B[idx];
        }
        return ret;
    }

    private void add(int idx, long val, long[] B) {
        int n=B.length;
        for(;idx<n;idx+=lowbit(idx)){
            B[idx]+=val;
        }
    }

    //input
    @SuppressWarnings("unused")
    private ArrayList<Integer>[] ng(int n, int m) {
        ArrayList<Integer>[] graph=(ArrayList<Integer>[])new ArrayList[n];
        for(int i=0;i<n;i++) {
            graph[i]=new ArrayList<>();
        }
        for(int i=1;i<=m;i++) {
            int s=in.nextInt()-1,e=in.nextInt()-1;
            graph[s].add(e);
            graph[e].add(s);
        }
        return graph;
    }

    private ArrayList<long[]>[] ngw(int n, int m) {
        ArrayList<long[]>[] graph=(ArrayList<long[]>[])new ArrayList[n];
        for(int i=0;i<n;i++) {
            graph[i]=new ArrayList<>();
        }
        for(int i=1;i<=m;i++) {
            long s=in.nextLong()-1,e=in.nextLong()-1,w=in.nextLong();
            graph[(int)s].add(new long[] {e,w});
            graph[(int)e].add(new long[] {s,w});
        }
        return graph;
    }

    private int ni() {
        return in.nextInt();
    }

    private long nl() {
        return in.nextLong();
    }
    private double nd() {
        return in.nextDouble();
    }
    private String ns() {
        return in.next();
    }

    private long[] na(int n) {
        long[] A=new long[n];
        for(int i=0;i<n;i++) {
            A[i]=in.nextLong();
        }
        return A;
    }

    private int[] nia(int n) {
        int[] A=new int[n];
        for(int i=0;i<n;i++) {
            A[i]=in.nextInt();
        }
        return A;
    }
}

class FastReader
{
    BufferedReader br;
    StringTokenizer st;
    InputStreamReader input;//no buffer
    public FastReader()
    {
        br=new BufferedReader(new InputStreamReader(System.in));
    }

    public FastReader(boolean isBuffer)
    {
        if(!isBuffer){
            input=new InputStreamReader(System.in);
        }else{
            br=new BufferedReader(new InputStreamReader(System.in));
        }
    }

    public boolean hasNext(){
        try{
            String s=br.readLine();
            if(s==null){
                return  false;
            }
            st=new StringTokenizer(s);
        }catch(IOException e){
            e.printStackTrace();
        }
        return true;
    }

    public String next()
    {   
        if(input!=null){
            try {
                StringBuilder sb=new StringBuilder();
                int ch=input.read();
                while(ch=='\n'||ch=='\r'||ch==32){
                    ch=input.read();
                }
                while(ch!='\n'&&ch!='\r'&&ch!=32){
                    sb.append((char)ch);
                    ch=input.read();
                }
                return sb.toString();
            }catch (Exception e){
                e.printStackTrace();
            }
        }
        while(st==null || !st.hasMoreElements())//回车，空行情况
        {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    public int nextInt()
    {
        return (int)nextLong();
    }

    public long nextLong() {
        try {
            if(input!=null){
                long ret=0;
                int b=input.read();
                while(b<'0'||b>'9'){
                    b=input.read();
                }
                while(b>='0'&&b<='9'){
                    ret=ret*10+(b-'0');
                    b=input.read();
                }
                return ret;
            }
        }catch (Exception e){
            e.printStackTrace();
        }
        return Long.parseLong(next());
    }

    public double nextDouble()
    {
        return Double.parseDouble(next());
    }
}