#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
constexpr int N = 1e5 + 5;
constexpr int mod = 1e9 + 7;
constexpr int LOG = 18;
template <typename T>
void dout(const T& x) {
  cout << x << ' ';
}
template <typename T, typename... Ts>
void dout(const T& v, const Ts&... args) {
  dout(v);
  dout(args...);
}
template <typename... Ts>
void vout(const Ts&... args) {
  dout(args...);
  cout << "\n";
  exit(0);
}
struct seg_tree {
  seg_tree(int n) : t(n << 2){};
  void upd(int pos, int i, int l, int r) {
    if (l + 1 == r) {
      t[i] = 1;
      return;
    }
    int mid = (l + r) >> 1;
    if (pos < mid)
      upd(pos, (i << 1) + 1, l, mid);
    else
      upd(pos, (i << 1) + 2, mid, r);
    t[i] = t[(i << 1) + 1] + t[(i << 1) + 2];
  }
  int get(int l, int r, int i, int cl, int cr) {
    if (l >= r) return 0;
    if (l == cl && r == cr) return t[i];
    int mid = (cl + cr) >> 1;
    return (get(l, min(mid, r), (i << 1) + 1, cl, mid) +
            get(max(l, mid), r, (i << 1) + 2, mid, cr));
  }
  void upd(int l, int r, ll val, int i, int cl, int cr) {
    if (l >= r) return;
    if (l == cl && r == cr) {
      t[i] += val;
      return;
    }
    int mid = (cl + cr) >> 1;
    upd(l, min(mid, r), val, (i << 1) + 1, cl, mid);
    upd(max(l, mid), r, val, (i << 1) + 2, mid, cr);
  }
  ll get(int pos, int i, int l, int r) {
    if (l + 1 == r) return t[i];
    int mid = (l + r) >> 1;
    return (t[i] + (pos < mid ? get(pos, (i << 1) + 1, l, mid)
                              : get(pos, (i << 1) + 2, mid, r)));
  }

 private:
  vector<ll> t;
};
int n;
vector<int> a;
void solve() {
  cin >> n;
  a.resize(n);
  for (int& v : a) cin >> v;
  ll pref_sum = 0;
  ll f = 0;
  ll s = 0;
  int m = *max_element(a.begin(), a.end());
  m++;
  seg_tree tr1(m);
  seg_tree tr2(m);
  int cnt = 0;
  for (int v : a) {
    pref_sum += v;
    f += pref_sum;
    cnt++;
    s += ll(v) * (cnt - 1);
    for (int i = 0, j = 0; i < m; i += v, j++) {
      f -= tr1.get(i, min(m, i + v), 0, 0, m) * ll(v) * j;
      tr2.upd(i, min(m, i + v), -j * ll(v), 0, 0, m);
    }
    s += tr2.get(v, 0, 0, m);
    tr1.upd(v, 0, 0, m);
    cout << f + s << ' ';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

### 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;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
constexpr int N = 1e5 + 5;
constexpr int mod = 1e9 + 7;
constexpr int LOG = 18;
template <typename T>
void dout(const T& x) {
  cout << x << ' ';
}
template <typename T, typename... Ts>
void dout(const T& v, const Ts&... args) {
  dout(v);
  dout(args...);
}
template <typename... Ts>
void vout(const Ts&... args) {
  dout(args...);
  cout << "\n";
  exit(0);
}
struct seg_tree {
  seg_tree(int n) : t(n << 2){};
  void upd(int pos, int i, int l, int r) {
    if (l + 1 == r) {
      t[i] = 1;
      return;
    }
    int mid = (l + r) >> 1;
    if (pos < mid)
      upd(pos, (i << 1) + 1, l, mid);
    else
      upd(pos, (i << 1) + 2, mid, r);
    t[i] = t[(i << 1) + 1] + t[(i << 1) + 2];
  }
  int get(int l, int r, int i, int cl, int cr) {
    if (l >= r) return 0;
    if (l == cl && r == cr) return t[i];
    int mid = (cl + cr) >> 1;
    return (get(l, min(mid, r), (i << 1) + 1, cl, mid) +
            get(max(l, mid), r, (i << 1) + 2, mid, cr));
  }
  void upd(int l, int r, ll val, int i, int cl, int cr) {
    if (l >= r) return;
    if (l == cl && r == cr) {
      t[i] += val;
      return;
    }
    int mid = (cl + cr) >> 1;
    upd(l, min(mid, r), val, (i << 1) + 1, cl, mid);
    upd(max(l, mid), r, val, (i << 1) + 2, mid, cr);
  }
  ll get(int pos, int i, int l, int r) {
    if (l + 1 == r) return t[i];
    int mid = (l + r) >> 1;
    return (t[i] + (pos < mid ? get(pos, (i << 1) + 1, l, mid)
                              : get(pos, (i << 1) + 2, mid, r)));
  }

 private:
  vector<ll> t;
};
int n;
vector<int> a;
void solve() {
  cin >> n;
  a.resize(n);
  for (int& v : a) cin >> v;
  ll pref_sum = 0;
  ll f = 0;
  ll s = 0;
  int m = *max_element(a.begin(), a.end());
  m++;
  seg_tree tr1(m);
  seg_tree tr2(m);
  int cnt = 0;
  for (int v : a) {
    pref_sum += v;
    f += pref_sum;
    cnt++;
    s += ll(v) * (cnt - 1);
    for (int i = 0, j = 0; i < m; i += v, j++) {
      f -= tr1.get(i, min(m, i + v), 0, 0, m) * ll(v) * j;
      tr2.upd(i, min(m, i + v), -j * ll(v), 0, 0, m);
    }
    s += tr2.get(v, 0, 0, m);
    tr1.upd(v, 0, 0, m);
    cout << f + s << ' ';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

```