#include <bits/stdc++.h>
using namespace std;
const long double pi = acos((long double)-1);
int in(int &a, int &b, int &c, int &d) {
  return scanf("%d%d%d%d", &a, &b, &c, &d);
}
int in(int &a, int &b, int &c) { return scanf("%d%d%d", &a, &b, &c); }
int in(int &a, int &b) { return scanf("%d%d", &a, &b); }
int in(long long &a, long long &b) { return scanf("%lld%lld", &a, &b); }
int in(long long &a, long long &b, long long &c, long long &d) {
  return scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
}
int in(long long &a, long long &b, long long &c) {
  return scanf("%lld%lld%lld", &a, &b, &c);
}
int in(long long &a) { return scanf("%lld", &a); }
int in(int &a) { return scanf("%d", &a); }
int in(char *s) { return scanf("%s", s); }
int in(char &c) { return scanf("%c", &c); }
void out(int a, bool ln) { printf("%d%c", a, " \n"[ln]); }
void out(long long a, bool ln) { printf("%lld%c", a, " \n"[ln]); }
void out(double a, int digit, bool ln) {
  printf("%.*f%c", digit, a, " \n"[ln]);
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int maxn = 3e5 + 5;
const int maxm = 1e6 + 5;
const long long mod = 1e9 + 7;
struct st {
  int l, r;
  long long len, lazy, sum;
} tree[maxn << 2];
void push_up(int root) {
  tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
}
void build(int l, int r, int root) {
  tree[root].l = l, tree[root].r = r, tree[root].len = r - l + 1;
  tree[root].lazy = 0;
  if (l == r) {
    tree[root].sum = 0;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, root << 1);
  build(mid + 1, r, root << 1 | 1);
  push_up(root);
}
void push_down(int root) {
  tree[root << 1].sum += tree[root].lazy * tree[root << 1].len;
  tree[root << 1 | 1].sum += tree[root].lazy * tree[root << 1 | 1].len;
  tree[root << 1].lazy += tree[root].lazy;
  tree[root << 1 | 1].lazy += tree[root].lazy;
  tree[root].lazy = 0;
}
void update(int l, int r, long long c, int root) {
  if (l <= tree[root].l && r >= tree[root].r) {
    tree[root].sum += tree[root].len * c;
    tree[root].lazy += c;
    return;
  }
  if (tree[root].lazy) push_down(root);
  int mid = (tree[root].l + tree[root].r) >> 1;
  if (l <= mid) update(l, r, c, root << 1);
  if (r > mid) update(l, r, c, root << 1 | 1);
  push_up(root);
}
long long query(int l, int r, int root) {
  if (l <= tree[root].l && r >= tree[root].r) {
    return tree[root].sum;
  }
  if (tree[root].lazy) push_down(root);
  int mid = (tree[root].l + tree[root].r) >> 1;
  long long ans = 0;
  if (l <= mid) ans += query(l, r, root << 1);
  if (r > mid) ans += query(l, r, root << 1 | 1);
  return ans;
}
int n;
long long a[maxn], ans[maxn];
int main() {
  in(n);
  build(1, 300000, 1);
  long long pre = 0;
  for (int i = 1; i <= n; ++i) {
    in(a[i]);
    ans[i] = a[i] * (i - 1) - query(a[i], a[i], 1);
    for (long long k = 1, j = a[i]; j <= 300000; k++, j += a[i]) {
      update(j, min(1LL * 300000, j + a[i] - 1), k * a[i], 1);
    }
  }
  build(1, 300000, 1);
  for (int i = 1; i <= n; ++i) {
    ans[i] += pre;
    pre += a[i];
    for (long long k = 1, j = a[i]; j <= 300000; k++, j += a[i]) {
      ans[i] -= query(j, min(1LL * 300000, j + a[i] - 1), 1) * a[i] * k;
    }
    update(a[i], a[i], 1, 1);
    ans[i] += ans[i - 1];
    out(ans[i], i == n);
  }
}

### Prompt

Your challenge is to write 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;
const long double pi = acos((long double)-1);
int in(int &a, int &b, int &c, int &d) {
  return scanf("%d%d%d%d", &a, &b, &c, &d);
}
int in(int &a, int &b, int &c) { return scanf("%d%d%d", &a, &b, &c); }
int in(int &a, int &b) { return scanf("%d%d", &a, &b); }
int in(long long &a, long long &b) { return scanf("%lld%lld", &a, &b); }
int in(long long &a, long long &b, long long &c, long long &d) {
  return scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
}
int in(long long &a, long long &b, long long &c) {
  return scanf("%lld%lld%lld", &a, &b, &c);
}
int in(long long &a) { return scanf("%lld", &a); }
int in(int &a) { return scanf("%d", &a); }
int in(char *s) { return scanf("%s", s); }
int in(char &c) { return scanf("%c", &c); }
void out(int a, bool ln) { printf("%d%c", a, " \n"[ln]); }
void out(long long a, bool ln) { printf("%lld%c", a, " \n"[ln]); }
void out(double a, int digit, bool ln) {
  printf("%.*f%c", digit, a, " \n"[ln]);
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int maxn = 3e5 + 5;
const int maxm = 1e6 + 5;
const long long mod = 1e9 + 7;
struct st {
  int l, r;
  long long len, lazy, sum;
} tree[maxn << 2];
void push_up(int root) {
  tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
}
void build(int l, int r, int root) {
  tree[root].l = l, tree[root].r = r, tree[root].len = r - l + 1;
  tree[root].lazy = 0;
  if (l == r) {
    tree[root].sum = 0;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, root << 1);
  build(mid + 1, r, root << 1 | 1);
  push_up(root);
}
void push_down(int root) {
  tree[root << 1].sum += tree[root].lazy * tree[root << 1].len;
  tree[root << 1 | 1].sum += tree[root].lazy * tree[root << 1 | 1].len;
  tree[root << 1].lazy += tree[root].lazy;
  tree[root << 1 | 1].lazy += tree[root].lazy;
  tree[root].lazy = 0;
}
void update(int l, int r, long long c, int root) {
  if (l <= tree[root].l && r >= tree[root].r) {
    tree[root].sum += tree[root].len * c;
    tree[root].lazy += c;
    return;
  }
  if (tree[root].lazy) push_down(root);
  int mid = (tree[root].l + tree[root].r) >> 1;
  if (l <= mid) update(l, r, c, root << 1);
  if (r > mid) update(l, r, c, root << 1 | 1);
  push_up(root);
}
long long query(int l, int r, int root) {
  if (l <= tree[root].l && r >= tree[root].r) {
    return tree[root].sum;
  }
  if (tree[root].lazy) push_down(root);
  int mid = (tree[root].l + tree[root].r) >> 1;
  long long ans = 0;
  if (l <= mid) ans += query(l, r, root << 1);
  if (r > mid) ans += query(l, r, root << 1 | 1);
  return ans;
}
int n;
long long a[maxn], ans[maxn];
int main() {
  in(n);
  build(1, 300000, 1);
  long long pre = 0;
  for (int i = 1; i <= n; ++i) {
    in(a[i]);
    ans[i] = a[i] * (i - 1) - query(a[i], a[i], 1);
    for (long long k = 1, j = a[i]; j <= 300000; k++, j += a[i]) {
      update(j, min(1LL * 300000, j + a[i] - 1), k * a[i], 1);
    }
  }
  build(1, 300000, 1);
  for (int i = 1; i <= n; ++i) {
    ans[i] += pre;
    pre += a[i];
    for (long long k = 1, j = a[i]; j <= 300000; k++, j += a[i]) {
      ans[i] -= query(j, min(1LL * 300000, j + a[i] - 1), 1) * a[i] * k;
    }
    update(a[i], a[i], 1, 1);
    ans[i] += ans[i - 1];
    out(ans[i], i == n);
  }
}

```