#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
bool chmin(A& a, B b) {
  return b < a ? a = b, true : false;
}
template <typename A, typename B>
bool chmax(A& a, B b) {
  return b > a ? a = b, true : false;
}
const int inf = 1e09 + 5e3;
const long long linf = 2e18 + 5e3;
const int mod = 1e9 + 7;
const int mxn = 2e4 + 30;
struct fenwickTree {
  long long n;
  vector<long long> ft;
  fenwickTree(long long z) {
    ft.resize(z + 1);
    n = z;
  }
  void updateSum(long long idx, long long k) {
    while (idx <= n) {
      ft[idx] += k;
      idx += (idx & (-1 * idx));
    }
  }
  long long querySum(long long idx) {
    long long sum = 0;
    while (idx > 0) {
      sum += ft[idx];
      idx -= (idx & (-1 * idx));
    }
    return sum;
  }
  long long query(long long l, long long r) {
    return querySum(r) - querySum(l - 1);
  }
};
struct segmentTree {
  vector<long long> sTree, lazy;
  long long N;
  segmentTree(long long n) {
    N = 1;
    while (N < n) {
      N <<= 1;
    }
    sTree.resize(N << 1);
    lazy.resize(N << 1);
  }
  long long query(long long left, long long right) {
    return query(1, 1, N, left, right);
  }
  long long query(long long node, long long curLeft, long long curRight,
                  long long left, long long right) {
    if (curLeft > right || curRight < left) return 0;
    if (curLeft >= left && curRight <= right) {
      return sTree[node];
    }
    long long mid = (curLeft + curRight) >> 1;
    long long leftChild = node << 1, rightChild = node << 1 | 1;
    propagate(node, curLeft, mid, curRight);
    long long q1 = query(leftChild, curLeft, mid, left, right);
    long long q2 = query(rightChild, mid + 1, curRight, left, right);
    return q1 + q2;
  }
  long long query_poll(long long i) { return query_poll(1, 1, N, i); }
  long long query_poll(long long node, long long curLeft, long long curRight,
                       long long idx) {
    if (curLeft == curRight) {
      return sTree[node];
    }
    long long mid = (curLeft + curRight) >> 1;
    long long leftChild = node << 1, rightChild = node << 1 | 1;
    propagate(node, curLeft, mid, curRight);
    if (idx <= mid) {
      return query_poll(leftChild, curLeft, mid, idx);
    }
    return query_poll(rightChild, mid + 1, curRight, idx);
  }
  void update_range(long long i, long long j, long long val) {
    update_range(1, 1, N, i, j, val);
  }
  void update_range(long long node, long long curLeft, long long curRight,
                    long long left, long long right, long long val) {
    if (curLeft > right || curRight < left) return;
    if (curLeft >= left && curRight <= right) {
      sTree[node] += (curRight - curLeft + 1) * val;
      lazy[node] += val;
      return;
    }
    long long mid = (curLeft + curRight) >> 1;
    long long leftChild = node << 1, rightChild = node << 1 | 1;
    propagate(node, curLeft, mid, curRight);
    update_range(leftChild, curLeft, mid, left, right, val);
    update_range(rightChild, mid + 1, curRight, left, right, val);
    sTree[node] = sTree[leftChild] + sTree[rightChild];
  }
  void update_Poll(long long i, long long val) { update_Poll(1, 1, N, i, val); }
  void update_Poll(long long node, long long curLeft, long long curRight,
                   long long idx, long long val) {
    if (curLeft == curRight) {
      sTree[node] = val;
      lazy[node] = val;
      return;
    }
    long long mid = (curLeft + curRight) >> 1;
    long long leftChild = node << 1, rightChild = node << 1 | 1;
    propagate(node, curLeft, mid, curRight);
    if (idx <= mid)
      update_Poll(leftChild, curLeft, mid, idx, val);
    else
      update_Poll(rightChild, mid + 1, curRight, idx, val);
    sTree[node] = sTree[leftChild] + sTree[rightChild];
  }
  void propagate(long long node, long long b, long long mid, long long e) {
    lazy[node << 1] += lazy[node];
    lazy[node << 1 | 1] += lazy[node];
    sTree[node << 1] += (mid - b + 1) * lazy[node];
    sTree[node << 1 | 1] += (e - mid) * lazy[node];
    lazy[node] = 0;
  }
};
void solve() {
  long long n;
  cin >> n;
  long long in[n];
  for (long long i = 0; i < n; i++) cin >> in[i];
  long long maxn = 300000;
  fenwickTree ft(maxn + 1);
  fenwickTree vals(maxn + 1);
  vector<long long> ans(n);
  ft.updateSum(in[0], 1);
  vals.updateSum(in[0], in[0]);
  for (long long i = 1; i < n; i++) {
    for (long long j = 0, mul = 0; j <= maxn; mul++) {
      long long nxt = min(j + in[i] - 1, maxn);
      ans[i] += (vals.query(j, nxt) - mul * 1ll * ft.query(j, nxt) * in[i]);
      j = nxt + 1;
    }
    ft.updateSum(in[i], 1);
    vals.updateSum(in[i], in[i]);
  }
  segmentTree st(maxn + 1);
  segmentTree stvals(maxn + 1);
  for (long long i = n - 1; i >= 0; i--) {
    for (long long j = 0, mul = 0; j <= maxn; mul++) {
      long long nxt = min(j + in[i] - 1, maxn);
      st.update_range(j == 0 ? 1 : j, nxt, 1);
      stvals.update_range(j == 0 ? 1 : j, nxt, in[i] * 1ll * mul);
      j = nxt + 1;
    }
    st.update_Poll(in[i], 0);
    stvals.update_Poll(in[i], 0);
  }
  for (long long i = 0; i < n; i++) {
    ans[i] += (st.query_poll(in[i]) * 1ll * in[i] - stvals.query_poll(in[i]));
    if (i > 0) ans[i] += ans[i - 1];
  }
  for (int i = 0; i < n; i++) cout << ans[i] << " ";
  cout << endl;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  solve();
}

### Prompt

Your task is to create a CPP solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
bool chmin(A& a, B b) {
  return b < a ? a = b, true : false;
}
template <typename A, typename B>
bool chmax(A& a, B b) {
  return b > a ? a = b, true : false;
}
const int inf = 1e09 + 5e3;
const long long linf = 2e18 + 5e3;
const int mod = 1e9 + 7;
const int mxn = 2e4 + 30;
struct fenwickTree {
  long long n;
  vector<long long> ft;
  fenwickTree(long long z) {
    ft.resize(z + 1);
    n = z;
  }
  void updateSum(long long idx, long long k) {
    while (idx <= n) {
      ft[idx] += k;
      idx += (idx & (-1 * idx));
    }
  }
  long long querySum(long long idx) {
    long long sum = 0;
    while (idx > 0) {
      sum += ft[idx];
      idx -= (idx & (-1 * idx));
    }
    return sum;
  }
  long long query(long long l, long long r) {
    return querySum(r) - querySum(l - 1);
  }
};
struct segmentTree {
  vector<long long> sTree, lazy;
  long long N;
  segmentTree(long long n) {
    N = 1;
    while (N < n) {
      N <<= 1;
    }
    sTree.resize(N << 1);
    lazy.resize(N << 1);
  }
  long long query(long long left, long long right) {
    return query(1, 1, N, left, right);
  }
  long long query(long long node, long long curLeft, long long curRight,
                  long long left, long long right) {
    if (curLeft > right || curRight < left) return 0;
    if (curLeft >= left && curRight <= right) {
      return sTree[node];
    }
    long long mid = (curLeft + curRight) >> 1;
    long long leftChild = node << 1, rightChild = node << 1 | 1;
    propagate(node, curLeft, mid, curRight);
    long long q1 = query(leftChild, curLeft, mid, left, right);
    long long q2 = query(rightChild, mid + 1, curRight, left, right);
    return q1 + q2;
  }
  long long query_poll(long long i) { return query_poll(1, 1, N, i); }
  long long query_poll(long long node, long long curLeft, long long curRight,
                       long long idx) {
    if (curLeft == curRight) {
      return sTree[node];
    }
    long long mid = (curLeft + curRight) >> 1;
    long long leftChild = node << 1, rightChild = node << 1 | 1;
    propagate(node, curLeft, mid, curRight);
    if (idx <= mid) {
      return query_poll(leftChild, curLeft, mid, idx);
    }
    return query_poll(rightChild, mid + 1, curRight, idx);
  }
  void update_range(long long i, long long j, long long val) {
    update_range(1, 1, N, i, j, val);
  }
  void update_range(long long node, long long curLeft, long long curRight,
                    long long left, long long right, long long val) {
    if (curLeft > right || curRight < left) return;
    if (curLeft >= left && curRight <= right) {
      sTree[node] += (curRight - curLeft + 1) * val;
      lazy[node] += val;
      return;
    }
    long long mid = (curLeft + curRight) >> 1;
    long long leftChild = node << 1, rightChild = node << 1 | 1;
    propagate(node, curLeft, mid, curRight);
    update_range(leftChild, curLeft, mid, left, right, val);
    update_range(rightChild, mid + 1, curRight, left, right, val);
    sTree[node] = sTree[leftChild] + sTree[rightChild];
  }
  void update_Poll(long long i, long long val) { update_Poll(1, 1, N, i, val); }
  void update_Poll(long long node, long long curLeft, long long curRight,
                   long long idx, long long val) {
    if (curLeft == curRight) {
      sTree[node] = val;
      lazy[node] = val;
      return;
    }
    long long mid = (curLeft + curRight) >> 1;
    long long leftChild = node << 1, rightChild = node << 1 | 1;
    propagate(node, curLeft, mid, curRight);
    if (idx <= mid)
      update_Poll(leftChild, curLeft, mid, idx, val);
    else
      update_Poll(rightChild, mid + 1, curRight, idx, val);
    sTree[node] = sTree[leftChild] + sTree[rightChild];
  }
  void propagate(long long node, long long b, long long mid, long long e) {
    lazy[node << 1] += lazy[node];
    lazy[node << 1 | 1] += lazy[node];
    sTree[node << 1] += (mid - b + 1) * lazy[node];
    sTree[node << 1 | 1] += (e - mid) * lazy[node];
    lazy[node] = 0;
  }
};
void solve() {
  long long n;
  cin >> n;
  long long in[n];
  for (long long i = 0; i < n; i++) cin >> in[i];
  long long maxn = 300000;
  fenwickTree ft(maxn + 1);
  fenwickTree vals(maxn + 1);
  vector<long long> ans(n);
  ft.updateSum(in[0], 1);
  vals.updateSum(in[0], in[0]);
  for (long long i = 1; i < n; i++) {
    for (long long j = 0, mul = 0; j <= maxn; mul++) {
      long long nxt = min(j + in[i] - 1, maxn);
      ans[i] += (vals.query(j, nxt) - mul * 1ll * ft.query(j, nxt) * in[i]);
      j = nxt + 1;
    }
    ft.updateSum(in[i], 1);
    vals.updateSum(in[i], in[i]);
  }
  segmentTree st(maxn + 1);
  segmentTree stvals(maxn + 1);
  for (long long i = n - 1; i >= 0; i--) {
    for (long long j = 0, mul = 0; j <= maxn; mul++) {
      long long nxt = min(j + in[i] - 1, maxn);
      st.update_range(j == 0 ? 1 : j, nxt, 1);
      stvals.update_range(j == 0 ? 1 : j, nxt, in[i] * 1ll * mul);
      j = nxt + 1;
    }
    st.update_Poll(in[i], 0);
    stvals.update_Poll(in[i], 0);
  }
  for (long long i = 0; i < n; i++) {
    ans[i] += (st.query_poll(in[i]) * 1ll * in[i] - stvals.query_poll(in[i]));
    if (i > 0) ans[i] += ans[i - 1];
  }
  for (int i = 0; i < n; i++) cout << ans[i] << " ";
  cout << endl;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  solve();
}

```