#include <bits/stdc++.h>
template <class T>
class Bit {
 public:
  T a[524288];
  void add(int x, T k) {
    while (x < 524288) a[x] += k, x += x + 1 & ~x;
  }
  T qry(int x) {
    T res = 0;
    while (x >= 0) res += a[x], x -= x + 1 & ~x;
    return res;
  }
};
Bit<int> bit_cnt;
Bit<long long int> bit_sum;
std::set<int> st;
int a[524288];
long long int p[524288];
long long int cache[512];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  for (int i = 0; i < n; ++i) {
    long long int cur_sum = bit_sum.qry(a[i]);
    int x = 1e9;
    for (int j = 1; j < 512; ++j) {
      x = a[i] / (j + 1);
      long long int nx_sum = bit_sum.qry(x);
      if (cur_sum - nx_sum == 0) break;
      p[i] -= (cur_sum - nx_sum) * j;
      cur_sum = nx_sum;
    }
    p[i] += (long long int)a[i] * (bit_cnt.a[524288 - 1] - bit_cnt.qry(x));
    for (auto k : st) {
      if (k > x) break;
      p[i] += a[i] % k;
    }
    if (a[i] < 512)
      p[i] += cache[a[i]];
    else {
      int tt = bit_cnt.a[524288 - 1];
      p[i] += bit_sum.a[524288 - 1];
      long long int sc = 0;
      for (int j = 1; a[i] * j - 1 < 524288; ++j) {
        int cnt = tt - bit_cnt.qry(a[i] * j - 1);
        if (!cnt) break;
        sc += cnt;
      }
      p[i] -= a[i] * sc;
    }
    bit_cnt.add(a[i], 1);
    bit_sum.add(a[i], a[i]);
    st.insert(a[i]);
    for (int j = 1; j < 512; ++j) cache[j] += a[i] % j;
  }
  for (int i = 1; i < n; ++i) p[i] += p[i - 1];
  for (int i = 0; i < n; ++i) printf(" %lld" + !i, p[i]);
  printf("\n");
  return 0;
}

### 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>
template <class T>
class Bit {
 public:
  T a[524288];
  void add(int x, T k) {
    while (x < 524288) a[x] += k, x += x + 1 & ~x;
  }
  T qry(int x) {
    T res = 0;
    while (x >= 0) res += a[x], x -= x + 1 & ~x;
    return res;
  }
};
Bit<int> bit_cnt;
Bit<long long int> bit_sum;
std::set<int> st;
int a[524288];
long long int p[524288];
long long int cache[512];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  for (int i = 0; i < n; ++i) {
    long long int cur_sum = bit_sum.qry(a[i]);
    int x = 1e9;
    for (int j = 1; j < 512; ++j) {
      x = a[i] / (j + 1);
      long long int nx_sum = bit_sum.qry(x);
      if (cur_sum - nx_sum == 0) break;
      p[i] -= (cur_sum - nx_sum) * j;
      cur_sum = nx_sum;
    }
    p[i] += (long long int)a[i] * (bit_cnt.a[524288 - 1] - bit_cnt.qry(x));
    for (auto k : st) {
      if (k > x) break;
      p[i] += a[i] % k;
    }
    if (a[i] < 512)
      p[i] += cache[a[i]];
    else {
      int tt = bit_cnt.a[524288 - 1];
      p[i] += bit_sum.a[524288 - 1];
      long long int sc = 0;
      for (int j = 1; a[i] * j - 1 < 524288; ++j) {
        int cnt = tt - bit_cnt.qry(a[i] * j - 1);
        if (!cnt) break;
        sc += cnt;
      }
      p[i] -= a[i] * sc;
    }
    bit_cnt.add(a[i], 1);
    bit_sum.add(a[i], a[i]);
    st.insert(a[i]);
    for (int j = 1; j < 512; ++j) cache[j] += a[i] % j;
  }
  for (int i = 1; i < n; ++i) p[i] += p[i - 1];
  for (int i = 0; i < n; ++i) printf(" %lld" + !i, p[i]);
  printf("\n");
  return 0;
}

```