#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
int n;
int a[300007];
long long ans[300007];
class uptree {
 public:
  pair<long long, int> tr[4 * 300007];
  void init(int where, int IL, int IR) {
    tr[where] = {0, 0};
    if (IL == IR) {
      return;
    }
    int mid = (IL + IR) / 2;
    init(2 * where, IL, mid);
    init(2 * where + 1, mid + 1, IR);
  }
  void update(int where, int IL, int IR, int pos) {
    if (IR < pos || pos < IL) {
      return;
    }
    if (IL == IR) {
      tr[where].first += pos;
      ++tr[where].second;
      return;
    }
    int mid = (IL + IR) / 2;
    if (pos <= mid) {
      update(2 * where, IL, mid, pos);
    } else {
      update(2 * where + 1, mid + 1, IR, pos);
    }
    tr[where].first = tr[2 * where].first + tr[2 * where + 1].first;
    tr[where].second = tr[2 * where].second + tr[2 * where + 1].second;
  }
  pair<long long, int> act = {0, 0};
  void query(int where, int IL, int IR, int CURL, int CURR) {
    if (IL > IR || CURL > CURR) {
      return;
    }
    if (IR < CURL || CURR < IL) {
      return;
    }
    if (CURL <= IL && IR <= CURR) {
      act.first += tr[where].first;
      act.second += tr[where].second;
      return;
    }
    int mid = (IL + IR) / 2;
    query(2 * where, IL, mid, CURL, CURR);
    query(2 * where + 1, mid + 1, IR, CURL, CURR);
  }
};
uptree uptr;
class downtr {
 public:
  long long offset[4 * 300007];
  long long cnt[4 * 300007];
  void init(int where, int IL, int IR) {
    offset[where] = cnt[where] = 0;
    if (IL == IR) {
      return;
    }
    int mid = (IL + IR) / 2;
    init(2 * where, IL, mid);
    init(2 * where + 1, mid + 1, IR);
  }
  int tot = 1;
  void update(int where, int IL, int IR, int CURL, int CURR) {
    if (IL > IR || CURL > CURR) {
      return;
    }
    if (IR < CURL || CURR < IL) {
      return;
    }
    if (CURL <= IL && IR <= CURR) {
      offset[where] += tot;
      ++cnt[where];
      tot += (IR - IL + 1);
      return;
    }
    int mid = (IL + IR) / 2;
    update(2 * where, IL, mid, CURL, CURR);
    update(2 * where + 1, mid + 1, IR, CURL, CURR);
  }
  long long ret = 0;
  void query(int where, int IL, int IR, int pos) {
    ret += offset[where] + (pos - IL) * cnt[where];
    if (IL == IR) {
      return;
    }
    int mid = (IL + IR) / 2;
    if (pos <= mid) {
      query(2 * where, IL, mid, pos);
    } else {
      query(2 * where + 1, mid + 1, IR, pos);
    }
  }
};
downtr dwtr;
void input() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
}
void solve() {
  uptr.init(1, 1, 300000);
  dwtr.init(1, 1, 300000);
  for (int i = 1; i <= n; ++i) {
    ans[i] = ans[i - 1];
    dwtr.ret = 0;
    dwtr.query(1, 1, 300000, a[i]);
    ans[i] += dwtr.ret;
    uptr.act = {0, 0};
    uptr.query(1, 1, 300000, 1, a[i] - 1);
    ans[i] += uptr.act.first;
    for (int j = 0; j <= 300000; j += a[i]) {
      int en = j + a[i] - 1;
      if (en > 300000) {
        en = 300000;
      }
      if (j > 0) {
        uptr.act = {0, 0};
        uptr.query(1, 1, 300000, j, en);
        pair<long long, int> ret = uptr.act;
        ans[i] += ret.first - 1LL * ret.second * j;
      }
      dwtr.tot = 1;
      dwtr.update(1, 1, 300000, j + 1, en);
    }
    uptr.update(1, 1, 300000, a[i]);
  }
  for (int i = 1; i <= n; ++i) {
    cout << ans[i] << " ";
  }
  cout << "\n";
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  t = 1;
  while (t--) {
    input();
    solve();
  }
  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;
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
int n;
int a[300007];
long long ans[300007];
class uptree {
 public:
  pair<long long, int> tr[4 * 300007];
  void init(int where, int IL, int IR) {
    tr[where] = {0, 0};
    if (IL == IR) {
      return;
    }
    int mid = (IL + IR) / 2;
    init(2 * where, IL, mid);
    init(2 * where + 1, mid + 1, IR);
  }
  void update(int where, int IL, int IR, int pos) {
    if (IR < pos || pos < IL) {
      return;
    }
    if (IL == IR) {
      tr[where].first += pos;
      ++tr[where].second;
      return;
    }
    int mid = (IL + IR) / 2;
    if (pos <= mid) {
      update(2 * where, IL, mid, pos);
    } else {
      update(2 * where + 1, mid + 1, IR, pos);
    }
    tr[where].first = tr[2 * where].first + tr[2 * where + 1].first;
    tr[where].second = tr[2 * where].second + tr[2 * where + 1].second;
  }
  pair<long long, int> act = {0, 0};
  void query(int where, int IL, int IR, int CURL, int CURR) {
    if (IL > IR || CURL > CURR) {
      return;
    }
    if (IR < CURL || CURR < IL) {
      return;
    }
    if (CURL <= IL && IR <= CURR) {
      act.first += tr[where].first;
      act.second += tr[where].second;
      return;
    }
    int mid = (IL + IR) / 2;
    query(2 * where, IL, mid, CURL, CURR);
    query(2 * where + 1, mid + 1, IR, CURL, CURR);
  }
};
uptree uptr;
class downtr {
 public:
  long long offset[4 * 300007];
  long long cnt[4 * 300007];
  void init(int where, int IL, int IR) {
    offset[where] = cnt[where] = 0;
    if (IL == IR) {
      return;
    }
    int mid = (IL + IR) / 2;
    init(2 * where, IL, mid);
    init(2 * where + 1, mid + 1, IR);
  }
  int tot = 1;
  void update(int where, int IL, int IR, int CURL, int CURR) {
    if (IL > IR || CURL > CURR) {
      return;
    }
    if (IR < CURL || CURR < IL) {
      return;
    }
    if (CURL <= IL && IR <= CURR) {
      offset[where] += tot;
      ++cnt[where];
      tot += (IR - IL + 1);
      return;
    }
    int mid = (IL + IR) / 2;
    update(2 * where, IL, mid, CURL, CURR);
    update(2 * where + 1, mid + 1, IR, CURL, CURR);
  }
  long long ret = 0;
  void query(int where, int IL, int IR, int pos) {
    ret += offset[where] + (pos - IL) * cnt[where];
    if (IL == IR) {
      return;
    }
    int mid = (IL + IR) / 2;
    if (pos <= mid) {
      query(2 * where, IL, mid, pos);
    } else {
      query(2 * where + 1, mid + 1, IR, pos);
    }
  }
};
downtr dwtr;
void input() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
}
void solve() {
  uptr.init(1, 1, 300000);
  dwtr.init(1, 1, 300000);
  for (int i = 1; i <= n; ++i) {
    ans[i] = ans[i - 1];
    dwtr.ret = 0;
    dwtr.query(1, 1, 300000, a[i]);
    ans[i] += dwtr.ret;
    uptr.act = {0, 0};
    uptr.query(1, 1, 300000, 1, a[i] - 1);
    ans[i] += uptr.act.first;
    for (int j = 0; j <= 300000; j += a[i]) {
      int en = j + a[i] - 1;
      if (en > 300000) {
        en = 300000;
      }
      if (j > 0) {
        uptr.act = {0, 0};
        uptr.query(1, 1, 300000, j, en);
        pair<long long, int> ret = uptr.act;
        ans[i] += ret.first - 1LL * ret.second * j;
      }
      dwtr.tot = 1;
      dwtr.update(1, 1, 300000, j + 1, en);
    }
    uptr.update(1, 1, 300000, a[i]);
  }
  for (int i = 1; i <= n; ++i) {
    cout << ans[i] << " ";
  }
  cout << "\n";
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  t = 1;
  while (t--) {
    input();
    solve();
  }
  return 0;
}

```