#include <bits/stdc++.h>
using namespace std;
const long long inf = 1000000007;
const int maxn = 300010;
int vis[maxn], cnt[maxn];
long long sum[maxn];
int mod(int x, int u) {
  int ret = 0;
  for (int i = 2; i <= u; ++i)
    if (vis[i]) {
      ret += x % i;
    }
  return ret;
}
long long cal(int x) {
  long long ret = 0, xx = x;
  for (int i = 1;; ++i) {
    int d = x / (i + 1), u = x / i;
    if (u <= 600) {
      return ret + mod(x, u);
    }
    ret += xx * (cnt[u] - cnt[d]) - (sum[u] - sum[d]) * i;
  }
  return ret;
}
int main() {
  static int a[maxn];
  static long long p[maxn];
  int n, N = 300000;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i < n; i += 400) {
    int j = min(n, i + 400);
    for (int k = i; k < j; ++k) {
      long long ak = a[k];
      p[k] = cal(a[k]) + ak * (cnt[N] - cnt[a[k]]);
      for (int kk = 0; kk < N; kk += a[k]) {
        int rig = min(kk + a[k] - 1, N);
        p[k] += (sum[rig] - sum[kk]) - (long long)kk * (cnt[rig] - cnt[kk]);
      }
      for (int kk = i; kk < k; ++kk) {
        p[k] += a[kk] % a[k] + a[k] % a[kk];
      }
    }
    for (int k = i; k < j; ++k) {
      vis[a[k]] = 1;
    }
    for (int k = 1; k <= N; ++k) {
      cnt[k] = vis[k] + cnt[k - 1];
      sum[k] = vis[k] * k + sum[k - 1];
    }
  }
  long long pp = 0;
  for (int i = 0; i < n; ++i) {
    pp += p[i];
    printf("%lld ", pp);
  }
  puts("");
  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 long long inf = 1000000007;
const int maxn = 300010;
int vis[maxn], cnt[maxn];
long long sum[maxn];
int mod(int x, int u) {
  int ret = 0;
  for (int i = 2; i <= u; ++i)
    if (vis[i]) {
      ret += x % i;
    }
  return ret;
}
long long cal(int x) {
  long long ret = 0, xx = x;
  for (int i = 1;; ++i) {
    int d = x / (i + 1), u = x / i;
    if (u <= 600) {
      return ret + mod(x, u);
    }
    ret += xx * (cnt[u] - cnt[d]) - (sum[u] - sum[d]) * i;
  }
  return ret;
}
int main() {
  static int a[maxn];
  static long long p[maxn];
  int n, N = 300000;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i < n; i += 400) {
    int j = min(n, i + 400);
    for (int k = i; k < j; ++k) {
      long long ak = a[k];
      p[k] = cal(a[k]) + ak * (cnt[N] - cnt[a[k]]);
      for (int kk = 0; kk < N; kk += a[k]) {
        int rig = min(kk + a[k] - 1, N);
        p[k] += (sum[rig] - sum[kk]) - (long long)kk * (cnt[rig] - cnt[kk]);
      }
      for (int kk = i; kk < k; ++kk) {
        p[k] += a[kk] % a[k] + a[k] % a[kk];
      }
    }
    for (int k = i; k < j; ++k) {
      vis[a[k]] = 1;
    }
    for (int k = 1; k <= N; ++k) {
      cnt[k] = vis[k] + cnt[k - 1];
      sum[k] = vis[k] * k + sum[k - 1];
    }
  }
  long long pp = 0;
  for (int i = 0; i < n; ++i) {
    pp += p[i];
    printf("%lld ", pp);
  }
  puts("");
  return 0;
}

```