#include <bits/stdc++.h>
#pragma GCC optimize "Ofast"
using namespace std;
const int INF = 1e9 + 7;
const int mod = 31607;
const int N = 1e6 + 7;
const int T = 1 << 20;
long long tree[T + T];
long long ile[T + T];
pair<long long, int> suma(int pocz, int kon) {
  pocz += T;
  kon += T;
  pair<long long, int> ret = {tree[pocz], ile[pocz]};
  if (pocz != kon) {
    ret.first += tree[kon];
    ret.second += ile[kon];
  }
  while (pocz >> 1 != kon >> 1) {
    if (pocz % 2 == 0) {
      ret.first += tree[pocz + 1];
      ret.second += ile[pocz + 1];
    }
    if (kon & 1) {
      ret.first += tree[kon - 1];
      ret.second += ile[kon - 1];
    }
    pocz >>= 1;
    kon >>= 1;
  }
  return ret;
}
void ustaw(int poz, long long val, int il = 1) {
  poz += T;
  tree[poz] = val;
  ile[poz] = il;
  poz >>= 1;
  while (poz) {
    tree[poz] = tree[poz + poz] + tree[poz + poz + 1];
    ile[poz] = ile[poz + poz] + ile[poz + poz + 1];
    poz >>= 1;
  }
}
long long ans[N];
void solve() {
  int n;
  cin >> n;
  vector<pair<int, int> > input;
  vector<int> tab(n);
  vector<long long> pref(n);
  for (int i = 0; i < n; i++) {
    cin >> tab[i];
    pref[i] = tab[i] + (i == 0 ? 0 : pref[i - 1]);
    input.push_back({tab[i], i});
  }
  sort(input.begin(), input.end());
  set<pair<long long, int> > secik;
  int prev_val = -1;
  int ile_wszyscy = 0;
  for (auto& [val, id] : input) {
    if (prev_val != -1) {
      ile_wszyscy += val - prev_val;
      while ((int)secik.size()) {
        auto pom = *secik.begin();
        if (pom.first - ile_wszyscy <= 0) {
          secik.erase(pom);
          int kiedy = tab[pom.second] - val % tab[pom.second];
          secik.insert({kiedy + ile_wszyscy, pom.second});
          ustaw(pom.second, tab[pom.second] * (val / tab[pom.second]));
        } else
          break;
      }
    }
    auto drzewo = suma(0, id);
    ans[id] += 1ll * val * drzewo.second - drzewo.first;
    secik.insert({val + ile_wszyscy, id});
    ustaw(id, val);
    prev_val = val;
  }
  secik.clear();
  for (int i = 0; i < T + T; i++) tree[i] = ile[i] = 0;
  reverse(input.begin(), input.end());
  for (auto& [val, id] : input) {
    ans[id] += 1ll * suma(0, id).second * val;
    ustaw(id, val);
  }
  for (int i = 0; i < T + T; i++) ile[i] = tree[i] = 0;
  for (int i = 0; i < n; i++) {
    ans[i] += (i == 0 ? 0 : pref[i - 1]);
    for (int j = 1; tab[i] * j <= 3e5; j++)
      ans[i] -=
          1ll * j * tab[i] * suma(tab[i] * j, tab[i] * j + tab[i] - 1).second;
    ustaw(tab[i], 1);
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << ' ';
    ans[i + 1] += ans[i];
  }
  cout << '\n';
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int test = 1;
  for (int i = 0; i < test; i++) solve();
}

### Prompt

Create a solution in CPP for 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 "Ofast"
using namespace std;
const int INF = 1e9 + 7;
const int mod = 31607;
const int N = 1e6 + 7;
const int T = 1 << 20;
long long tree[T + T];
long long ile[T + T];
pair<long long, int> suma(int pocz, int kon) {
  pocz += T;
  kon += T;
  pair<long long, int> ret = {tree[pocz], ile[pocz]};
  if (pocz != kon) {
    ret.first += tree[kon];
    ret.second += ile[kon];
  }
  while (pocz >> 1 != kon >> 1) {
    if (pocz % 2 == 0) {
      ret.first += tree[pocz + 1];
      ret.second += ile[pocz + 1];
    }
    if (kon & 1) {
      ret.first += tree[kon - 1];
      ret.second += ile[kon - 1];
    }
    pocz >>= 1;
    kon >>= 1;
  }
  return ret;
}
void ustaw(int poz, long long val, int il = 1) {
  poz += T;
  tree[poz] = val;
  ile[poz] = il;
  poz >>= 1;
  while (poz) {
    tree[poz] = tree[poz + poz] + tree[poz + poz + 1];
    ile[poz] = ile[poz + poz] + ile[poz + poz + 1];
    poz >>= 1;
  }
}
long long ans[N];
void solve() {
  int n;
  cin >> n;
  vector<pair<int, int> > input;
  vector<int> tab(n);
  vector<long long> pref(n);
  for (int i = 0; i < n; i++) {
    cin >> tab[i];
    pref[i] = tab[i] + (i == 0 ? 0 : pref[i - 1]);
    input.push_back({tab[i], i});
  }
  sort(input.begin(), input.end());
  set<pair<long long, int> > secik;
  int prev_val = -1;
  int ile_wszyscy = 0;
  for (auto& [val, id] : input) {
    if (prev_val != -1) {
      ile_wszyscy += val - prev_val;
      while ((int)secik.size()) {
        auto pom = *secik.begin();
        if (pom.first - ile_wszyscy <= 0) {
          secik.erase(pom);
          int kiedy = tab[pom.second] - val % tab[pom.second];
          secik.insert({kiedy + ile_wszyscy, pom.second});
          ustaw(pom.second, tab[pom.second] * (val / tab[pom.second]));
        } else
          break;
      }
    }
    auto drzewo = suma(0, id);
    ans[id] += 1ll * val * drzewo.second - drzewo.first;
    secik.insert({val + ile_wszyscy, id});
    ustaw(id, val);
    prev_val = val;
  }
  secik.clear();
  for (int i = 0; i < T + T; i++) tree[i] = ile[i] = 0;
  reverse(input.begin(), input.end());
  for (auto& [val, id] : input) {
    ans[id] += 1ll * suma(0, id).second * val;
    ustaw(id, val);
  }
  for (int i = 0; i < T + T; i++) ile[i] = tree[i] = 0;
  for (int i = 0; i < n; i++) {
    ans[i] += (i == 0 ? 0 : pref[i - 1]);
    for (int j = 1; tab[i] * j <= 3e5; j++)
      ans[i] -=
          1ll * j * tab[i] * suma(tab[i] * j, tab[i] * j + tab[i] - 1).second;
    ustaw(tab[i], 1);
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << ' ';
    ans[i + 1] += ans[i];
  }
  cout << '\n';
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int test = 1;
  for (int i = 0; i < test; i++) solve();
}

```