#include <bits/stdc++.h>
using namespace std;
const int N = 300000;
int n;
long long ans = 0;
long long T1[N + 5];
long long T2[N + 5];
long long T3[N + 5];
void upd(long long *T, int x, int v) {
  while (x <= N) {
    T[x] += v, x += x & (-x);
  }
}
long long qry(long long *T, int x) {
  long long ret = 0;
  while (x > 0) ret += T[x], x -= x & (-x);
  return ret;
}
long long query(long long *T, int l, int r) {
  r = min(r, N);
  return qry(T, r) - qry(T, l - 1);
}
void update(int num, int th) {
  for (int i = 0; i * num <= N; ++i) {
    ans += query(T1, i * num, (i + 1) * num - 1) -
           query(T2, i * num, (i + 1) * num - 1) * i * num;
  }
  ans += 1ll * num * (th - 1) - query(T3, 1, num);
  upd(T1, num, num);
  upd(T2, num, 1);
  for (int i = num; i <= N; i += num) {
    upd(T3, i, num);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int num;
    scanf("%d", &num);
    update(num, 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;
const int N = 300000;
int n;
long long ans = 0;
long long T1[N + 5];
long long T2[N + 5];
long long T3[N + 5];
void upd(long long *T, int x, int v) {
  while (x <= N) {
    T[x] += v, x += x & (-x);
  }
}
long long qry(long long *T, int x) {
  long long ret = 0;
  while (x > 0) ret += T[x], x -= x & (-x);
  return ret;
}
long long query(long long *T, int l, int r) {
  r = min(r, N);
  return qry(T, r) - qry(T, l - 1);
}
void update(int num, int th) {
  for (int i = 0; i * num <= N; ++i) {
    ans += query(T1, i * num, (i + 1) * num - 1) -
           query(T2, i * num, (i + 1) * num - 1) * i * num;
  }
  ans += 1ll * num * (th - 1) - query(T3, 1, num);
  upd(T1, num, num);
  upd(T2, num, 1);
  for (int i = num; i <= N; i += num) {
    upd(T3, i, num);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int num;
    scanf("%d", &num);
    update(num, i);
    printf("%lld ", ans);
  }
  return 0;
}

```