description: 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
solution: #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;
  }
  