#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast", "unroll-loops", "omit-frame-pointer", "inline")
#pragma GCC option("arch=native", "tune-native", "no-zero-upper");
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
const long long MX = 3e5 + 10;
long long N;
bool ex[MX];
struct fen {
  long long pref[MX];
  long long cnt[MX];
  long long lsone(long long x) { return x & (-x); }
  void upd(long long p, long long v) {
    for (; p < MX; p += lsone(p)) cnt[p]++, pref[p] += v;
  }
  pair<long long, long long> rs(long long a, long long b) {
    long long sum = 0;
    long long num = 0;
    for (; b; b -= lsone(b)) sum += pref[b], num += cnt[b];
    for (; a; a -= lsone(a)) sum -= pref[a], num -= cnt[a];
    return make_pair(sum, num);
  }
} ft;
struct fen2 {
  long long pref[MX];
  long long lsone(long long x) { return x & (-x); }
  void upd(long long p) {
    long long n = p;
    for (; p < MX; p += lsone(p)) pref[p] += n;
  }
  long long rs(long long b) {
    long long sum = 0;
    for (; b; b -= lsone(b)) sum += pref[b];
    return sum;
  }
} ft2;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N;
  long long bound = 2000;
  long long ans = 0;
  for (long long i = 0; i < N; i++) {
    long long v;
    cin >> v;
    ft.upd(v, -v);
    ft2.upd(v);
    ex[v] = true;
    if (i == 0) {
      cout << 0;
      continue;
    }
    {
      ans += ft2.rs(v - 1);
      for (long long j = 1; j <= bound && j < v; j++)
        if (ex[j]) ans += v % j;
      long long nx = min(v, bound + 1);
      while (nx < v) {
        long long div = v / nx, rg = div == 1 ? v - 1 : v / div;
        pair<long long, long long> temp = ft.rs(nx - 1, rg);
        ans += 1ll * (temp.first + 1ll * temp.second * rg) * div +
               1ll * temp.second * (v % rg);
        nx = rg + 1;
      }
    }
    {
      pair<long long, long long> temp = ft.rs(v, MX - 1);
      ans += 1ll * v * temp.second;
      for (long long j = v + 1; j <= bound; j++)
        if (ex[j]) ans += j % v;
      long long nx = max(v + 1, bound + 1);
      while (nx < MX) {
        long long div = nx / v,
                  rg = v * (div + 1) > MX ? MX - 1 : v * (div + 1) - 1;
        pair<long long, long long> temp = ft.rs(nx - 1, rg);
        temp.first = -temp.first;
        ans += 1ll * (temp.first - 1ll * temp.second * nx) +
               1ll * temp.second * (nx % v);
        nx = rg + 1;
      }
    }
    cout << " " << ans;
  }
  cout << '\n';
}

### Prompt

Generate 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;
#pragma GCC optimize("Ofast", "unroll-loops", "omit-frame-pointer", "inline")
#pragma GCC option("arch=native", "tune-native", "no-zero-upper");
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
const long long MX = 3e5 + 10;
long long N;
bool ex[MX];
struct fen {
  long long pref[MX];
  long long cnt[MX];
  long long lsone(long long x) { return x & (-x); }
  void upd(long long p, long long v) {
    for (; p < MX; p += lsone(p)) cnt[p]++, pref[p] += v;
  }
  pair<long long, long long> rs(long long a, long long b) {
    long long sum = 0;
    long long num = 0;
    for (; b; b -= lsone(b)) sum += pref[b], num += cnt[b];
    for (; a; a -= lsone(a)) sum -= pref[a], num -= cnt[a];
    return make_pair(sum, num);
  }
} ft;
struct fen2 {
  long long pref[MX];
  long long lsone(long long x) { return x & (-x); }
  void upd(long long p) {
    long long n = p;
    for (; p < MX; p += lsone(p)) pref[p] += n;
  }
  long long rs(long long b) {
    long long sum = 0;
    for (; b; b -= lsone(b)) sum += pref[b];
    return sum;
  }
} ft2;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N;
  long long bound = 2000;
  long long ans = 0;
  for (long long i = 0; i < N; i++) {
    long long v;
    cin >> v;
    ft.upd(v, -v);
    ft2.upd(v);
    ex[v] = true;
    if (i == 0) {
      cout << 0;
      continue;
    }
    {
      ans += ft2.rs(v - 1);
      for (long long j = 1; j <= bound && j < v; j++)
        if (ex[j]) ans += v % j;
      long long nx = min(v, bound + 1);
      while (nx < v) {
        long long div = v / nx, rg = div == 1 ? v - 1 : v / div;
        pair<long long, long long> temp = ft.rs(nx - 1, rg);
        ans += 1ll * (temp.first + 1ll * temp.second * rg) * div +
               1ll * temp.second * (v % rg);
        nx = rg + 1;
      }
    }
    {
      pair<long long, long long> temp = ft.rs(v, MX - 1);
      ans += 1ll * v * temp.second;
      for (long long j = v + 1; j <= bound; j++)
        if (ex[j]) ans += j % v;
      long long nx = max(v + 1, bound + 1);
      while (nx < MX) {
        long long div = nx / v,
                  rg = v * (div + 1) > MX ? MX - 1 : v * (div + 1) - 1;
        pair<long long, long long> temp = ft.rs(nx - 1, rg);
        temp.first = -temp.first;
        ans += 1ll * (temp.first - 1ll * temp.second * nx) +
               1ll * temp.second * (nx % v);
        nx = rg + 1;
      }
    }
    cout << " " << ans;
  }
  cout << '\n';
}

```