#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<ld, ld>;
using cd = complex<ld>;
using vcd = vector<cd>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<ld>;
using vs = vector<string>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T> >;
template <class T>
inline int ckmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int ckmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
template <class T>
void remDup(vector<T>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), end(v));
}
constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int bits(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }
constexpr int p2(int x) { return 1 << x; }
constexpr int msk2(int x) { return p2(x) - 1; }
ll ceilDiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll floorDiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
void setPrec(int x) { cout << fixed << setprecision(x); }
string to_string(char c) { return string(1, c); }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
string to_string(bool b) { return to_string((int)b); }
template <class T>
string to_string(complex<T> c) {
  stringstream ss;
  ss << c;
  return ss.str();
}
template <class T>
using V = vector<T>;
string to_string(V<bool> v) {
  string res = "{";
  for (int i = (0); i <= (int((v).size()) - 1); i++) res += char('0' + v[i]);
  res += "}";
  return res;
}
template <size_t sz>
string to_string(bitset<sz> b) {
  string res = "";
  for (int i = (0); i <= (int((b).size()) - 1); i++) res += char('0' + b[i]);
  return res;
}
template <class T, class U>
string to_string(pair<T, U> p);
template <class T>
string to_string(T v) {
  bool fst = 1;
  string res = "";
  for (const auto& x : v) {
    if (!fst) res += " ";
    fst = 0;
    res += to_string(x);
  }
  return res;
}
template <class T, class U>
string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class T>
void pr(T x) {
  cout << to_string(x);
}
template <class T, class... U>
void pr(const T& t, const U&... u) {
  pr(t);
  pr(u...);
}
void ps() { pr("\n"); }
template <class T, class... U>
void ps(const T& t, const U&... u) {
  pr(t);
  if (sizeof...(u)) pr(" ");
  ps(u...);
}
void DBG() { cerr << "]" << endl; }
template <class T, class... U>
void DBG(const T& t, const U&... u) {
  cerr << to_string(t);
  if (sizeof...(u)) cerr << ", ";
  DBG(u...);
}
const ld PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld EPS = 1e-9;
const ll MODBASE = 1000000007LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 200010;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;
struct BinaryIndexedTree {
 public:
  BinaryIndexedTree(int n) {
    N = n;
    t.resize(N + 1);
    for (int i = (0); i <= (N); i++) t[i] = 0;
  }
  void update(int u, int val) {
    while (u <= N) {
      t[u] += val;
      u = u + (u & (-u));
    }
  }
  ll get(int u) {
    if (u > N) u = N;
    ll res = 0;
    while (u) {
      res += t[u];
      u = u - (u & (-u));
    }
    return res;
  }

 private:
  vector<ll> t;
  int N;
};
int n, a[MAXN];
ll getRange(BinaryIndexedTree& bit, int l, int r) {
  if (l > r) return 0;
  if (l == 0) return bit.get(r);
  return bit.get(r) - bit.get(l - 1);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  cin >> n;
  for (int i = (1); i <= (n); i++) cin >> a[i];
  BinaryIndexedTree sumBIT(300000), numBIT(300000), sumLowerBIT(300000);
  ll res = 0;
  for (int i = (1); i <= (n); i++) {
    ll cur = 0;
    for (int j = 0; j <= 300000; j += a[i]) {
      ll x = getRange(sumBIT, j, j + a[i] - 1);
      ll y = getRange(numBIT, j, j + a[i] - 1);
      cur += x - y * j;
    }
    cur += getRange(numBIT, a[i] + 1, 300000) * a[i];
    ll num = getRange(numBIT, 1, a[i]);
    ll sum = getRange(sumLowerBIT, 1, a[i]);
    cur += a[i] * num - sum;
    res += cur;
    cout << res << ' ';
    sumBIT.update(a[i], a[i]);
    numBIT.update(a[i], 1);
    for (int j = a[i]; j <= 300000; j += a[i]) {
      sumLowerBIT.update(j, a[i]);
    }
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 ll = long long;
using ld = double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<ld, ld>;
using cd = complex<ld>;
using vcd = vector<cd>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<ld>;
using vs = vector<string>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T> >;
template <class T>
inline int ckmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int ckmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
template <class T>
void remDup(vector<T>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), end(v));
}
constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int bits(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }
constexpr int p2(int x) { return 1 << x; }
constexpr int msk2(int x) { return p2(x) - 1; }
ll ceilDiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll floorDiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
void setPrec(int x) { cout << fixed << setprecision(x); }
string to_string(char c) { return string(1, c); }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
string to_string(bool b) { return to_string((int)b); }
template <class T>
string to_string(complex<T> c) {
  stringstream ss;
  ss << c;
  return ss.str();
}
template <class T>
using V = vector<T>;
string to_string(V<bool> v) {
  string res = "{";
  for (int i = (0); i <= (int((v).size()) - 1); i++) res += char('0' + v[i]);
  res += "}";
  return res;
}
template <size_t sz>
string to_string(bitset<sz> b) {
  string res = "";
  for (int i = (0); i <= (int((b).size()) - 1); i++) res += char('0' + b[i]);
  return res;
}
template <class T, class U>
string to_string(pair<T, U> p);
template <class T>
string to_string(T v) {
  bool fst = 1;
  string res = "";
  for (const auto& x : v) {
    if (!fst) res += " ";
    fst = 0;
    res += to_string(x);
  }
  return res;
}
template <class T, class U>
string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class T>
void pr(T x) {
  cout << to_string(x);
}
template <class T, class... U>
void pr(const T& t, const U&... u) {
  pr(t);
  pr(u...);
}
void ps() { pr("\n"); }
template <class T, class... U>
void ps(const T& t, const U&... u) {
  pr(t);
  if (sizeof...(u)) pr(" ");
  ps(u...);
}
void DBG() { cerr << "]" << endl; }
template <class T, class... U>
void DBG(const T& t, const U&... u) {
  cerr << to_string(t);
  if (sizeof...(u)) cerr << ", ";
  DBG(u...);
}
const ld PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld EPS = 1e-9;
const ll MODBASE = 1000000007LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 200010;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;
struct BinaryIndexedTree {
 public:
  BinaryIndexedTree(int n) {
    N = n;
    t.resize(N + 1);
    for (int i = (0); i <= (N); i++) t[i] = 0;
  }
  void update(int u, int val) {
    while (u <= N) {
      t[u] += val;
      u = u + (u & (-u));
    }
  }
  ll get(int u) {
    if (u > N) u = N;
    ll res = 0;
    while (u) {
      res += t[u];
      u = u - (u & (-u));
    }
    return res;
  }

 private:
  vector<ll> t;
  int N;
};
int n, a[MAXN];
ll getRange(BinaryIndexedTree& bit, int l, int r) {
  if (l > r) return 0;
  if (l == 0) return bit.get(r);
  return bit.get(r) - bit.get(l - 1);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  cin >> n;
  for (int i = (1); i <= (n); i++) cin >> a[i];
  BinaryIndexedTree sumBIT(300000), numBIT(300000), sumLowerBIT(300000);
  ll res = 0;
  for (int i = (1); i <= (n); i++) {
    ll cur = 0;
    for (int j = 0; j <= 300000; j += a[i]) {
      ll x = getRange(sumBIT, j, j + a[i] - 1);
      ll y = getRange(numBIT, j, j + a[i] - 1);
      cur += x - y * j;
    }
    cur += getRange(numBIT, a[i] + 1, 300000) * a[i];
    ll num = getRange(numBIT, 1, a[i]);
    ll sum = getRange(sumLowerBIT, 1, a[i]);
    cur += a[i] * num - sum;
    res += cur;
    cout << res << ' ';
    sumBIT.update(a[i], a[i]);
    numBIT.update(a[i], 1);
    for (int j = a[i]; j <= 300000; j += a[i]) {
      sumLowerBIT.update(j, a[i]);
    }
  }
  return 0;
}

```