#include <bits/stdc++.h>
using namespace std;
template <typename M, typename N>
istream& operator>>(istream& is, pair<M, N>& p) {
  is >> p.first >> p.second;
  return is;
}
template <typename M>
istream& operator>>(istream& is, vector<M>& v) {
  for (auto& it : v) is >> it;
  return is;
}
template <typename M>
istream& operator>>(istream& is, vector<vector<M>>& v) {
  for (auto& it : v) is >> it;
  return is;
}
template <typename M, typename N>
ostream& operator<<(ostream& os, const pair<M, N>& p) {
  os << p.first << ' ' << p.second << '\n';
  return os;
}
template <typename M>
ostream& operator<<(ostream& os, const vector<M>& v) {
  for (auto it : v) os << it << ' ';
  cout << '\n';
  return os;
}
template <typename M>
ostream& operator<<(ostream& os, const vector<vector<M>>& v) {
  for (auto it : v) os << it;
  return os;
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int a, int b) { return rng() % (b - a + 1) + a; }
const long double eps = 1e-7;
const long double pi = acos(-1);
const long long inf = (long long)1e9 + 10;
const int mod = 998244353;
int n, m, k;
const int N = 6e5 + 20;
struct fenwicktree {
  vector<long long int> bit;
  int n;
  template <typename M>
  fenwicktree(M size) {
    n = size + 10;
    bit.resize(n);
  }
  template <typename M>
  fenwicktree(vector<M>& a) {
    n = (int)a.size() + 1;
    bit.resize(n);
    for (int i = 0; i < n - 1; i++) {
      add(i, a[i]);
    }
  }
  long long int query(int j) {
    long long int ans = 0;
    for (++j; j; j -= j & -j) {
      ans += bit[j];
    }
    return ans;
  }
  long long int query(int i, int j) { return query(j) - query(i - 1); }
  void add(int id, int val) {
    for (++id; id < n; id += id & -id) {
      bit[id] += val;
    }
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  fenwicktree sum(N), no(N), multiples(N);
  vector<long long> ans(n + 1);
  long long u;
  for (int i = 1; i <= n; i++) {
    cin >> u;
    ans[i] += no.query(0, N) * u - multiples.query(0, (int)u);
    for (int j = (int)u; j < N; j += u) {
      if (u != 1) {
        ans[i] += sum.query(j - (int)u + 1, j - 1) -
                  no.query(j - (int)u + 1, j - 1) * (long long)(j - u);
      }
      multiples.add(j, (int)u);
    }
    sum.add((int)u, (int)u);
    no.add((int)u, (int)1);
    ans[i] += ans[i - 1];
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << ' ';
  }
  cout << '\n';
  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;
template <typename M, typename N>
istream& operator>>(istream& is, pair<M, N>& p) {
  is >> p.first >> p.second;
  return is;
}
template <typename M>
istream& operator>>(istream& is, vector<M>& v) {
  for (auto& it : v) is >> it;
  return is;
}
template <typename M>
istream& operator>>(istream& is, vector<vector<M>>& v) {
  for (auto& it : v) is >> it;
  return is;
}
template <typename M, typename N>
ostream& operator<<(ostream& os, const pair<M, N>& p) {
  os << p.first << ' ' << p.second << '\n';
  return os;
}
template <typename M>
ostream& operator<<(ostream& os, const vector<M>& v) {
  for (auto it : v) os << it << ' ';
  cout << '\n';
  return os;
}
template <typename M>
ostream& operator<<(ostream& os, const vector<vector<M>>& v) {
  for (auto it : v) os << it;
  return os;
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int a, int b) { return rng() % (b - a + 1) + a; }
const long double eps = 1e-7;
const long double pi = acos(-1);
const long long inf = (long long)1e9 + 10;
const int mod = 998244353;
int n, m, k;
const int N = 6e5 + 20;
struct fenwicktree {
  vector<long long int> bit;
  int n;
  template <typename M>
  fenwicktree(M size) {
    n = size + 10;
    bit.resize(n);
  }
  template <typename M>
  fenwicktree(vector<M>& a) {
    n = (int)a.size() + 1;
    bit.resize(n);
    for (int i = 0; i < n - 1; i++) {
      add(i, a[i]);
    }
  }
  long long int query(int j) {
    long long int ans = 0;
    for (++j; j; j -= j & -j) {
      ans += bit[j];
    }
    return ans;
  }
  long long int query(int i, int j) { return query(j) - query(i - 1); }
  void add(int id, int val) {
    for (++id; id < n; id += id & -id) {
      bit[id] += val;
    }
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  fenwicktree sum(N), no(N), multiples(N);
  vector<long long> ans(n + 1);
  long long u;
  for (int i = 1; i <= n; i++) {
    cin >> u;
    ans[i] += no.query(0, N) * u - multiples.query(0, (int)u);
    for (int j = (int)u; j < N; j += u) {
      if (u != 1) {
        ans[i] += sum.query(j - (int)u + 1, j - 1) -
                  no.query(j - (int)u + 1, j - 1) * (long long)(j - u);
      }
      multiples.add(j, (int)u);
    }
    sum.add((int)u, (int)u);
    no.add((int)u, (int)1);
    ans[i] += ans[i - 1];
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << ' ';
  }
  cout << '\n';
  return 0;
}

```