#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937 eng(seed);
long long random2() { return (1ll << 31ll) * eng() + eng(); }
struct FT {
  vector<long long> s;
  FT(int n) : s(n) {}
  void update(int pos, long long dif) {
    for (; pos < (int)(s).size(); pos |= pos + 1) s[pos] += dif;
  }
  long long query(int pos) {
    long long res = 0;
    for (; pos > 0; pos &= pos - 1) res += s[pos - 1];
    return res;
  }
  int lower_bound(long long sum) {
    if (sum <= 0) return -1;
    int pos = 0;
    for (int pw = 1 << 25; pw; pw >>= 1) {
      if (pos + pw <= (int)(s).size() && s[pos + pw - 1] < sum)
        pos += pw, sum -= s[pos - 1];
    }
    return pos;
  }
};
long long n, m, k, q, T;
const long long big = 1000000007;
const long long big2 = 1000000009;
const long long mod = 998244353;
const int MAXN = 600001;
const int SQRT = 500;
vector<int> smalls;
vector<long long> A;
long long amod[SQRT] = {0};
long long bigs = 0;
long long brute(long long i) {
  long long res = 0;
  for (int c1 = 0; c1 < (i + 1); ++c1) {
    for (int c2 = 0; c2 < (i + 1); ++c2) {
      res += A[c1] % A[c2];
    }
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long a, b, c, d, e;
  cin >> n;
  FT ft1(MAXN);
  FT ft2(MAXN);
  long long upscore = 0;
  long long ans = 0;
  for (int c1 = 0; c1 < (n); ++c1) {
    cin >> a;
    A.push_back(a);
    if (a < SQRT) {
      ans += amod[a];
      ans += ft2.query(a) + a * bigs;
      for (auto& y : smalls) {
        ans += a % y;
      }
      smalls.push_back(a);
    } else {
      long long temp1 = upscore;
      long long a2 = a;
      while (1) {
        temp1 -= (long long(c1) - ft1.query(a2)) * a;
        if (a2 > MAXN / 2) break;
        a2 += a;
      }
      ans += temp1;
      ans += ft2.query(a) + a * bigs;
      for (auto& y : smalls) {
        ans += a % y;
      }
      a2 = a;
      while (1) {
        ft2.update(a2 - 1, -a);
        if (a2 > MAXN / 2) break;
        a2 += a;
      }
      bigs++;
    }
    ft1.update(a, 1);
    for (int c2 = 1; c2 < (SQRT); ++c2) {
      amod[c2] += a % c2;
    }
    upscore += a;
    cout << ans << " ";
  }
  return 0;
}

### 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>
#pragma GCC optimize("O3")
using namespace std;
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937 eng(seed);
long long random2() { return (1ll << 31ll) * eng() + eng(); }
struct FT {
  vector<long long> s;
  FT(int n) : s(n) {}
  void update(int pos, long long dif) {
    for (; pos < (int)(s).size(); pos |= pos + 1) s[pos] += dif;
  }
  long long query(int pos) {
    long long res = 0;
    for (; pos > 0; pos &= pos - 1) res += s[pos - 1];
    return res;
  }
  int lower_bound(long long sum) {
    if (sum <= 0) return -1;
    int pos = 0;
    for (int pw = 1 << 25; pw; pw >>= 1) {
      if (pos + pw <= (int)(s).size() && s[pos + pw - 1] < sum)
        pos += pw, sum -= s[pos - 1];
    }
    return pos;
  }
};
long long n, m, k, q, T;
const long long big = 1000000007;
const long long big2 = 1000000009;
const long long mod = 998244353;
const int MAXN = 600001;
const int SQRT = 500;
vector<int> smalls;
vector<long long> A;
long long amod[SQRT] = {0};
long long bigs = 0;
long long brute(long long i) {
  long long res = 0;
  for (int c1 = 0; c1 < (i + 1); ++c1) {
    for (int c2 = 0; c2 < (i + 1); ++c2) {
      res += A[c1] % A[c2];
    }
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long a, b, c, d, e;
  cin >> n;
  FT ft1(MAXN);
  FT ft2(MAXN);
  long long upscore = 0;
  long long ans = 0;
  for (int c1 = 0; c1 < (n); ++c1) {
    cin >> a;
    A.push_back(a);
    if (a < SQRT) {
      ans += amod[a];
      ans += ft2.query(a) + a * bigs;
      for (auto& y : smalls) {
        ans += a % y;
      }
      smalls.push_back(a);
    } else {
      long long temp1 = upscore;
      long long a2 = a;
      while (1) {
        temp1 -= (long long(c1) - ft1.query(a2)) * a;
        if (a2 > MAXN / 2) break;
        a2 += a;
      }
      ans += temp1;
      ans += ft2.query(a) + a * bigs;
      for (auto& y : smalls) {
        ans += a % y;
      }
      a2 = a;
      while (1) {
        ft2.update(a2 - 1, -a);
        if (a2 > MAXN / 2) break;
        a2 += a;
      }
      bigs++;
    }
    ft1.update(a, 1);
    for (int c2 = 1; c2 < (SQRT); ++c2) {
      amod[c2] += a % c2;
    }
    upscore += a;
    cout << ans << " ";
  }
  return 0;
}

```