#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
template <typename T>
T gcd(T a, T b) {
  return (b ? __gcd(a, b) : a);
}
template <typename T>
T lcm(T a, T b) {
  return (a * (b / gcd(a, b)));
}
template <typename T, typename T1>
T amax(T &a, T1 b) {
  if (b > a) a = b;
  return a;
}
template <typename T, typename T1>
T amin(T &a, T1 b) {
  if (b < a) a = b;
  return a;
}
template <typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &a) {
  in >> a.first >> a.second;
  return in;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> a) {
  out << "{" << a.first << ", " << a.second << "}";
  return out;
}
const int mod = 1e9 + 7;
template <typename T>
void print(T &a) {
  for (auto &x : a) cout << x << " ";
  cout << "\n";
}
const int N = 3e5 + 10;
const int maxn = N;
struct fenwick1 {
  long long A[maxn];
  long long query(int i) {
    long long sum = 0;
    while (i > 0) sum += A[i], i -= ((i) & -(i));
    return sum;
  }
  void update(int i, long long k) {
    if (i < 1) return;
    while (i < maxn) A[i] += k, i += ((i) & -(i));
  }
  void rupd(int l, int r, long long v) {
    update(l, v);
    update(r + 1, -v);
  }
} contribution;
struct fenwick {
  long long A[maxn];
  long long query(int i) {
    long long sum = 0;
    while (i > 0) sum += A[i], i -= ((i) & -(i));
    return sum;
  }
  void update(int i, long long k) {
    if (i < 1) return;
    while (i < maxn) A[i] += k, i += ((i) & -(i));
  }
  long long query(int l, int r) { return (query(r) - query(l - 1)); }
} cnt;
void solve() {
  int n;
  cin >> n;
  vector<long long> a(n);
  long long mx = 0;
  for (int i = 0; i < (n); i++) cin >> a[i];
  for (int i = 0; i < (n); i++) amax(mx, a[i]);
  vector<long long> ans(n);
  long long ps = 0;
  long long prev = 0;
  for (int i = 0; i < (n); i++) {
    long long x = a[i];
    long long tmp = a[i] * i;
    tmp -= contribution.query(a[i]);
    long long f = 1;
    while (x * f <= mx) {
      contribution.rupd(x * f, min(x * (f + 1) - 1, mx), x * f);
      f++;
    }
    long long tmp1 = ps;
    long long tmp2 = 0;
    f = 1;
    while (x * f <= mx) {
      tmp2 += f * cnt.query(x * f, min(x * (f + 1) - 1, mx));
      f++;
    }
    tmp1 -= x * tmp2;
    cnt.update(a[i], 1);
    ans[i] = prev + tmp + tmp1;
    prev = ans[i];
    ps += a[i];
  }
  print(ans);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  auto start1 = high_resolution_clock::now();
  int t = 1;
  while (t--) {
    solve();
  }
  auto stop1 = high_resolution_clock::now();
  auto duration = duration_cast<milliseconds>(stop1 - start1);
  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>
using namespace std;
using namespace chrono;
template <typename T>
T gcd(T a, T b) {
  return (b ? __gcd(a, b) : a);
}
template <typename T>
T lcm(T a, T b) {
  return (a * (b / gcd(a, b)));
}
template <typename T, typename T1>
T amax(T &a, T1 b) {
  if (b > a) a = b;
  return a;
}
template <typename T, typename T1>
T amin(T &a, T1 b) {
  if (b < a) a = b;
  return a;
}
template <typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &a) {
  in >> a.first >> a.second;
  return in;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> a) {
  out << "{" << a.first << ", " << a.second << "}";
  return out;
}
const int mod = 1e9 + 7;
template <typename T>
void print(T &a) {
  for (auto &x : a) cout << x << " ";
  cout << "\n";
}
const int N = 3e5 + 10;
const int maxn = N;
struct fenwick1 {
  long long A[maxn];
  long long query(int i) {
    long long sum = 0;
    while (i > 0) sum += A[i], i -= ((i) & -(i));
    return sum;
  }
  void update(int i, long long k) {
    if (i < 1) return;
    while (i < maxn) A[i] += k, i += ((i) & -(i));
  }
  void rupd(int l, int r, long long v) {
    update(l, v);
    update(r + 1, -v);
  }
} contribution;
struct fenwick {
  long long A[maxn];
  long long query(int i) {
    long long sum = 0;
    while (i > 0) sum += A[i], i -= ((i) & -(i));
    return sum;
  }
  void update(int i, long long k) {
    if (i < 1) return;
    while (i < maxn) A[i] += k, i += ((i) & -(i));
  }
  long long query(int l, int r) { return (query(r) - query(l - 1)); }
} cnt;
void solve() {
  int n;
  cin >> n;
  vector<long long> a(n);
  long long mx = 0;
  for (int i = 0; i < (n); i++) cin >> a[i];
  for (int i = 0; i < (n); i++) amax(mx, a[i]);
  vector<long long> ans(n);
  long long ps = 0;
  long long prev = 0;
  for (int i = 0; i < (n); i++) {
    long long x = a[i];
    long long tmp = a[i] * i;
    tmp -= contribution.query(a[i]);
    long long f = 1;
    while (x * f <= mx) {
      contribution.rupd(x * f, min(x * (f + 1) - 1, mx), x * f);
      f++;
    }
    long long tmp1 = ps;
    long long tmp2 = 0;
    f = 1;
    while (x * f <= mx) {
      tmp2 += f * cnt.query(x * f, min(x * (f + 1) - 1, mx));
      f++;
    }
    tmp1 -= x * tmp2;
    cnt.update(a[i], 1);
    ans[i] = prev + tmp + tmp1;
    prev = ans[i];
    ps += a[i];
  }
  print(ans);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  auto start1 = high_resolution_clock::now();
  int t = 1;
  while (t--) {
    solve();
  }
  auto stop1 = high_resolution_clock::now();
  auto duration = duration_cast<milliseconds>(stop1 - start1);
  return 0;
}

```