#include <bits/stdc++.h>
using namespace std;
inline char nc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int read() {
  register int x = 0, f = 1;
  register char ch = nc();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = nc();
  }
  while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = nc();
  return x * f;
}
inline void write(register int x) {
  if (!x) putchar('0');
  if (x < 0) x = -x, putchar('-');
  static int sta[20];
  register int tot = 0;
  while (x) sta[tot++] = x % 10, x /= 10;
  while (tot) putchar(sta[--tot] + 48);
}
int n, a[300005];
long long ans, sm;
long long bl1[5005], bl2[5005];
long long tr1[300005 * 20], tr2[300005 * 20];
void modify(int x) {
  for (int i = x / 560; i < 560; ++i) ++bl1[i], bl2[i] += x;
  int rb = (x / 560 + 1) * 560;
  for (int i = x; i < rb; ++i) ++tr1[i], tr2[i] += x;
}
long long qry1(int x) { return (x >= 560 ? bl1[x / 560 - 1] : 0) + tr1[x]; }
long long qry2(int x) { return (x >= 560 ? bl2[x / 560 - 1] : 0) + tr2[x]; }
long long rqry1(int l, int r) { return qry1(r) - qry1(l - 1); }
long long rqry2(int l, int r) { return qry2(r) - qry2(l - 1); }
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    ans += sm;
    ans += 1ll * a[i] * (i - 1);
    for (int l = 1, r; l < a[i]; l = r + 1) {
      r = a[i] / (a[i] / l);
      if (r == a[i]) r = a[i] - 1;
      ans -= rqry2(l, r) * (a[i] / l);
    }
    for (int l = a[i], r = 2 * a[i] - 1, cnt = 1; l <= 300000;
         l += a[i], r += a[i], ++cnt)
      ans -= rqry1(l, min(r, 300000)) * a[i] * cnt;
    modify(a[i]);
    sm += a[i];
    printf("%lld ", ans);
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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;
inline char nc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int read() {
  register int x = 0, f = 1;
  register char ch = nc();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = nc();
  }
  while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = nc();
  return x * f;
}
inline void write(register int x) {
  if (!x) putchar('0');
  if (x < 0) x = -x, putchar('-');
  static int sta[20];
  register int tot = 0;
  while (x) sta[tot++] = x % 10, x /= 10;
  while (tot) putchar(sta[--tot] + 48);
}
int n, a[300005];
long long ans, sm;
long long bl1[5005], bl2[5005];
long long tr1[300005 * 20], tr2[300005 * 20];
void modify(int x) {
  for (int i = x / 560; i < 560; ++i) ++bl1[i], bl2[i] += x;
  int rb = (x / 560 + 1) * 560;
  for (int i = x; i < rb; ++i) ++tr1[i], tr2[i] += x;
}
long long qry1(int x) { return (x >= 560 ? bl1[x / 560 - 1] : 0) + tr1[x]; }
long long qry2(int x) { return (x >= 560 ? bl2[x / 560 - 1] : 0) + tr2[x]; }
long long rqry1(int l, int r) { return qry1(r) - qry1(l - 1); }
long long rqry2(int l, int r) { return qry2(r) - qry2(l - 1); }
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    ans += sm;
    ans += 1ll * a[i] * (i - 1);
    for (int l = 1, r; l < a[i]; l = r + 1) {
      r = a[i] / (a[i] / l);
      if (r == a[i]) r = a[i] - 1;
      ans -= rqry2(l, r) * (a[i] / l);
    }
    for (int l = a[i], r = 2 * a[i] - 1, cnt = 1; l <= 300000;
         l += a[i], r += a[i], ++cnt)
      ans -= rqry1(l, min(r, 300000)) * a[i] * cnt;
    modify(a[i]);
    sm += a[i];
    printf("%lld ", ans);
  }
  return 0;
}

```