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>
  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;
  }
  