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

public class Main {

    public static int MAX = 300009;
    public static long[] c = new long[MAX];
    public static long[] s = new long[MAX];
    public static long[][] segtree = new  long[4 * MAX][2];

    public static void update(int v, int l, int r, int tl, int tr, int x) {
        if (l > tr || r < tl || l > r || tl > tr) return;
        if (l == tl && r == tr) {
            segtree[v][0] += x;
            segtree[v][1] += 1;
        } else {
            int m = (l + r) / 2;
            update(v * 2 + 1, l, m, tl, Math.min(m, tr), x);
            update(v * 2 + 2, m + 1, r, Math.max(tl, m + 1), tr, x + Math.max(tl, m + 1) - tl);
        }
    }
    
    public static long sum(int v, int l, int r, int pos) {
        if (l > r) return 0;
        if (l == r){
            return segtree[v][0];
        }
        long ans = 0;
        int m = (l + r) / 2;
        if (pos <= m){
            ans += sum(v * 2 + 1, l, m, pos);
        } else {
            ans += sum(v * 2 + 2, m + 1, r, pos);
        }
        ans += segtree[v][0] + (pos - l) * segtree[v][1];
        return ans;
    }

    public static long sum(int r, long[] t) {
        long result = 0;
        if (r >= MAX) r = MAX - 1;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            result += t[r];
        return result;
    }

    public static void inc(int i, long delta, long[] t) {
        int n = t.length;
        if (i >= n) return;
        for (; i < n; i = (i | (i + 1)))
            t[i] += delta;
    }

    public static long sum(int l, int r, long[] t) {
        return sum(r, t) - sum(l - 1, t);
    }

    public static void main(String[] args) throws Exception {
        int n = r.readInt();
        int[] a = r.readIntArray(n);
        long[] p = new long[n];
        for (int i = 1; i < n; i++) {
            inc(a[i - 1], 1, c);
            inc(a[i - 1], a[i - 1], s);
            for (int j = a[i - 1]; j < MAX; j += a[i - 1]) {
                update(0, 0, MAX, j + 1, Math.min(j + a[i - 1] - 1, MAX), 1);
            }

            p[i] = p[i - 1];

            // a[j] % a[i]
            p[i] += sum(0, a[i] - 1, s);
            for (int j = a[i]; j < MAX; j += a[i]) {
                p[i] += sum(j, j + a[i] - 1, s) - j * sum(j, j + a[i] - 1, c);
            }

            // a[i] % a[j]
            p[i] += sum(a[i] + 1, MAX, c) * a[i];
            p[i] += sum(0, 0, MAX - 1, a[i]);
        }

        for (int i = 0; i < n; i++) {
            w.writer.print(p[i] + " ");
        }
        w.writer.flush();
    }

    static public InputReader r = new InputReader(System.in);
    static public OutputWriter w = new OutputWriter(System.out);

    static public class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int[] readIntArray(int n) {
            int[] array = new int[n];
            for (int i = 0; i < n; i++) {
                array[i] = this.readInt();
            }
            return array;
        }

        public long[] readLongArray(int n) {
            long[] array = new long[n];
            for (int i = 0; i < n; i++) {
                array[i] = this.readLong();
            }
            return array;
        }

        public long readLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    static public class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0)
                    writer.print(' ');
                writer.print(objects[i]);
            }
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }
    }
}