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
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <bitset>
#include <fstream>
#include <unordered_set>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <stack>
#include <queue>
#include <complex>


using namespace std;
using namespace __gnu_pbds;



/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")*/

/*#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,tune=native")
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")*/

#define int long long
#define ll long long
//#define int short int
#define eb emplace_back
#define pb push_back
#define ld long double
//#define ld double
#define mp make_pair
#define f first
#define s second
#define gleg(x) return cout << x, 0
#define pii pair <int, int>
#define deb(a) cerr << #a << " = " << a << '\n';
//#define sz(x) (int)s.size();
#define fast() {     ios_base::sync_with_stdio(0);     cin.tie(0);     cout << fixed << setprecision(9);     cerr << fixed << setprecision(12); }

template < typename firstType, typename secondType = null_type, class compare = less < firstType > >
struct sett {
    typedef tree <
            firstType,
            secondType,
            compare,
            rb_tree_tag,
            tree_order_statistics_node_update
    > _ ;
};


const int INF = 1e18 + 7;
const ld EPS = 1e-9;
const int MAXI = 350;
const int MOD = 998244353;
const int MOD1 = 1e9 + 7;
const int MAXST = 2000000;
const int P = 31;
const int P1 = 37;
const int N = 5100000;
const ld PI = 3.14159265358979323;
const int bp = 23;
//const int sz = 1 << bp;


ostream &operator<<(ostream &stream, const pair <int, int> &p) {
    stream << p.first << ' ' << p.second << ' ';
    return stream;
}

int a[210000];
int t[2040000], u[2040000];

void push(int v, int l, int r){
    if (u[v] != 0){
        t[v] += (r - l + 1) * u[v];

        if (l != r){
            u[v * 2] += u[v];
            u[v * 2 + 1] += u[v];
        }

        u[v] = 0;
    }
}

int get(int v, int l, int r, int pos){
    push(v, l, r);
    if (l == r)
        return t[v];
    else{
        int m = (r + l) / 2;
        if (pos <= m)
            return get(v * 2, l, m, pos);
        else
            return get(v * 2 + 1, m + 1, r, pos);

    }
}

int get(int pos){
    get(1, 0, 3e5 + 1, pos);
}

void update(int v, int l, int r, int l1, int r1, int val){
    push(v, l1, r1);
    if (l > r)
        return;
    if (l == l1 && r == r1) {
        u[v] += val;
        push(v, l1, r1);
    }
    else{
        int m = (r1 + l1) / 2;
        update(v * 2, l, min(r, m), l1, m, val);
        update(v * 2 + 1, max(l, m + 1), r, m + 1, r1, val);
        t[v] = t[v * 2] + t[v * 2 + 1];
    }
}

void update(int l, int r, int val){
    update(1, l, r, 0, 3e5 + 1, val);
}

int fns(int v, int l, int r, int l1, int r1){
    if (l > r)
        return 0;
    if (l == l1 && r == r1)
        return t[v];
    else{
        int m = (r1 + l1) / 2;
        return fns(v * 2, l, min(r, m), l1, m) + fns(v * 2 + 1, max(l, m + 1), r, m + 1, r1);
    }
}

int fns(int l, int r){
    return fns(1, l, r, 0, 3e5 + 1);
}

void upd(int v, int l, int r, int pos){
    if (l == r)
        t[v]++;
    else{
        int m = (r + l) / 2;
        if (pos <= m)
            upd(v * 2, l, m, pos);
        else
            upd(v * 2 + 1, m + 1, r, pos);
        t[v] = t[v * 2] + t[v * 2 + 1];
    }
}

void upd(int pos){
    upd(1, 0, 3e5 + 1, pos);
}

signed main(){
    fast();
    srand(time(0));
//    #ifdef LOCAL
    //freopen("rna.in", "r", stdin);
    //freopen("rna.out", "w", stdout);
//    #endif
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    vector <int> pref(n + 1);

    for (int i = 0; i < n; i++)
        pref[i + 1] = pref[i] + a[i];

    vector <int> ans(n, 0);

    for (int i = 0; i < n; i++){
        int g = get(a[i]);
        ans[i] = (i != 0 ? ans[i - 1] : 0) + a[i] * i - get(a[i]);

        for (int j = 1; j * a[i] <= 3e5; j++){
            update(j * a[i], min((int)3e5, (j + 1) * a[i] - 1), j * a[i]);
        }
    }

    vector <int> ans1(n, 0);
    fill(t, t + (int)(3e5 * 4), 0);
    for (int i = 0; i < n; i++){
        ans1[i] = (i != 0 ? ans1[i - 1] : 0) + pref[i];

        for (int j = 1; j * a[i] <= 3e5; j++){
            ans1[i] -= j * a[i] * fns(j * a[i], min((int)3e5, (j + 1) * a[i] - 1));
        }

        upd(a[i]);
    }

    for (int i = 0; i < n; i++)
        cout << ans[i] + ans1[i] << ' ';
    cout << '\n';
    return 0;
}
