#include <bits/stdc++.h>
using namespace std;
namespace gao {
int B = 512, N = 300001, tot = N / B;
long long sumb[1010], sumpre[303000];
long long cb[1010], cpre[303000];
void add(int pos) {
  for (int i = pos / B + 1; i <= tot; ++i) sumb[i] += pos, cb[i] += 1;
  for (int i = pos; i / B == pos / B; ++i) {
    sumpre[i] += pos, cpre[i] += 1;
  }
}
pair<long long, long long> que(int pos) {
  pos = min(pos, N);
  return (pair<long long, long long>){sumb[pos / B] + sumpre[pos],
                                      cb[pos / B] + cpre[pos]};
}
}  // namespace gao
int n;
long long ans;
const int maxn = 300000;
int main() {
  for (cin >> n; n--;) {
    int x;
    scanf("%d", &x);
    {
      pair<long long, long long> las = {0ll, 0ll};
      for (int i = 0; i * x <= maxn; ++i) {
        pair<long long, long long> now = gao::que((i + 1) * x - 1);
        long long sum = now.first - las.first, c = now.second - las.second;
        las = now;
        ans += sum - c * x * i;
      }
    }
    {
      pair<long long, long long> las = {0ll, 0ll};
      int i = 1, sqr = sqrt(x) - 3;
      for (; i < x;) {
        int ne = i;
        if (i >= sqr) ne = x / (x / i);
        pair<long long, long long> now = gao::que(ne);
        long long sum = now.first - las.first, c = now.second - las.second;
        las = now;
        ans += x * c - sum * (x / i);
        i = ne + 1;
      }
      ans += (gao::que(maxn).second - gao::que(x).second) * x;
    }
    gao::add(x);
    printf("%lld ", ans);
  }
  puts("");
}

### 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;
namespace gao {
int B = 512, N = 300001, tot = N / B;
long long sumb[1010], sumpre[303000];
long long cb[1010], cpre[303000];
void add(int pos) {
  for (int i = pos / B + 1; i <= tot; ++i) sumb[i] += pos, cb[i] += 1;
  for (int i = pos; i / B == pos / B; ++i) {
    sumpre[i] += pos, cpre[i] += 1;
  }
}
pair<long long, long long> que(int pos) {
  pos = min(pos, N);
  return (pair<long long, long long>){sumb[pos / B] + sumpre[pos],
                                      cb[pos / B] + cpre[pos]};
}
}  // namespace gao
int n;
long long ans;
const int maxn = 300000;
int main() {
  for (cin >> n; n--;) {
    int x;
    scanf("%d", &x);
    {
      pair<long long, long long> las = {0ll, 0ll};
      for (int i = 0; i * x <= maxn; ++i) {
        pair<long long, long long> now = gao::que((i + 1) * x - 1);
        long long sum = now.first - las.first, c = now.second - las.second;
        las = now;
        ans += sum - c * x * i;
      }
    }
    {
      pair<long long, long long> las = {0ll, 0ll};
      int i = 1, sqr = sqrt(x) - 3;
      for (; i < x;) {
        int ne = i;
        if (i >= sqr) ne = x / (x / i);
        pair<long long, long long> now = gao::que(ne);
        long long sum = now.first - las.first, c = now.second - las.second;
        las = now;
        ans += x * c - sum * (x / i);
        i = ne + 1;
      }
      ans += (gao::que(maxn).second - gao::que(x).second) * x;
    }
    gao::add(x);
    printf("%lld ", ans);
  }
  puts("");
}

```