#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 7;
struct nd {
  long long coeff, frq;
  long long sum;
};
nd tr[4 * MAXN];
long long lazy[4 * MAXN];
nd combine(const nd &a, const nd &b) {
  nd rt;
  rt.coeff = a.coeff + b.coeff;
  rt.frq = a.frq + b.frq;
  rt.sum = a.sum + b.sum;
  return rt;
}
void propagate(int u, int l, int r) {
  if (lazy[u]) {
    tr[u].sum += lazy[u] * tr[u].frq;
    tr[u].coeff += lazy[u];
    if (l != r) {
      lazy[u * 2] += lazy[u];
      lazy[u * 2 + 1] += lazy[u];
    }
    lazy[u] = 0;
  }
}
void update(int u, int l, int r, int x, int y, long long v) {
  propagate(u, l, r);
  if (r < x || y < l) return;
  if (x <= l && r <= y) {
    lazy[u] += v;
    propagate(u, l, r);
    return;
  }
  int mid = (l + r) / 2;
  update(u * 2, l, mid, x, y, v);
  update(u * 2 + 1, mid + 1, r, x, y, v);
  tr[u] = combine(tr[u * 2], tr[u * 2 + 1]);
}
void update(int u, int l, int r, int idx) {
  propagate(u, l, r);
  if (r < idx || idx < l) return;
  if (l == r) {
    tr[u].frq++;
    tr[u].sum += tr[u].coeff;
    return;
  }
  int mid = (l + r) / 2;
  update(u * 2, l, mid, idx);
  update(u * 2 + 1, mid + 1, r, idx);
  tr[u] = combine(tr[u * 2], tr[u * 2 + 1]);
}
nd query(int u, int l, int r, int x, int y) {
  propagate(u, l, r);
  if (x <= l && r <= y) return tr[u];
  int mid = (l + r) / 2;
  if (y <= mid) return query(u * 2, l, mid, x, y);
  if (mid < x) return query(u * 2 + 1, mid + 1, r, x, y);
  return combine(query(u * 2, l, mid, x, y),
                 query(u * 2 + 1, mid + 1, r, x, y));
}
long long a[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  long long mx = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    mx = max(mx, a[i]);
  }
  long long presum = 0;
  for (int k = 1; k <= n; k++) {
    for (int x = a[k]; x <= mx; x += a[k]) {
      update(1, 1, mx, x, mx, a[k]);
    }
    update(1, 1, mx, a[k]);
    presum += a[k];
    cout << presum * k - tr[1].sum << " ";
  }
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
const int MAXN = 3e5 + 7;
struct nd {
  long long coeff, frq;
  long long sum;
};
nd tr[4 * MAXN];
long long lazy[4 * MAXN];
nd combine(const nd &a, const nd &b) {
  nd rt;
  rt.coeff = a.coeff + b.coeff;
  rt.frq = a.frq + b.frq;
  rt.sum = a.sum + b.sum;
  return rt;
}
void propagate(int u, int l, int r) {
  if (lazy[u]) {
    tr[u].sum += lazy[u] * tr[u].frq;
    tr[u].coeff += lazy[u];
    if (l != r) {
      lazy[u * 2] += lazy[u];
      lazy[u * 2 + 1] += lazy[u];
    }
    lazy[u] = 0;
  }
}
void update(int u, int l, int r, int x, int y, long long v) {
  propagate(u, l, r);
  if (r < x || y < l) return;
  if (x <= l && r <= y) {
    lazy[u] += v;
    propagate(u, l, r);
    return;
  }
  int mid = (l + r) / 2;
  update(u * 2, l, mid, x, y, v);
  update(u * 2 + 1, mid + 1, r, x, y, v);
  tr[u] = combine(tr[u * 2], tr[u * 2 + 1]);
}
void update(int u, int l, int r, int idx) {
  propagate(u, l, r);
  if (r < idx || idx < l) return;
  if (l == r) {
    tr[u].frq++;
    tr[u].sum += tr[u].coeff;
    return;
  }
  int mid = (l + r) / 2;
  update(u * 2, l, mid, idx);
  update(u * 2 + 1, mid + 1, r, idx);
  tr[u] = combine(tr[u * 2], tr[u * 2 + 1]);
}
nd query(int u, int l, int r, int x, int y) {
  propagate(u, l, r);
  if (x <= l && r <= y) return tr[u];
  int mid = (l + r) / 2;
  if (y <= mid) return query(u * 2, l, mid, x, y);
  if (mid < x) return query(u * 2 + 1, mid + 1, r, x, y);
  return combine(query(u * 2, l, mid, x, y),
                 query(u * 2 + 1, mid + 1, r, x, y));
}
long long a[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  long long mx = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    mx = max(mx, a[i]);
  }
  long long presum = 0;
  for (int k = 1; k <= n; k++) {
    for (int x = a[k]; x <= mx; x += a[k]) {
      update(1, 1, mx, x, mx, a[k]);
    }
    update(1, 1, mx, a[k]);
    presum += a[k];
    cout << presum * k - tr[1].sum << " ";
  }
  return 0;
}

```