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;
  const long long inf = 1000000007;
  const int maxn = 300010;
  int vis[maxn], cnt[maxn];
  long long sum[maxn];
  int mod(int x, int u) {
    int ret = 0;
    for (int i = 2; i <= u; ++i)
      if (vis[i]) {
        ret += x % i;
      }
    return ret;
  }
  long long cal(int x) {
    long long ret = 0, xx = x;
    for (int i = 1;; ++i) {
      int d = x / (i + 1), u = x / i;
      if (u <= 600) {
        return ret + mod(x, u);
      }
      ret += xx * (cnt[u] - cnt[d]) - (sum[u] - sum[d]) * i;
    }
    return ret;
  }
  int main() {
    static int a[maxn];
    static long long p[maxn];
    int n, N = 300000;
    cin >> n;
    for (int i = 0; i < n; ++i) {
      scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i += 400) {
      int j = min(n, i + 400);
      for (int k = i; k < j; ++k) {
        long long ak = a[k];
        p[k] = cal(a[k]) + ak * (cnt[N] - cnt[a[k]]);
        for (int kk = 0; kk < N; kk += a[k]) {
          int rig = min(kk + a[k] - 1, N);
          p[k] += (sum[rig] - sum[kk]) - (long long)kk * (cnt[rig] - cnt[kk]);
        }
        for (int kk = i; kk < k; ++kk) {
          p[k] += a[kk] % a[k] + a[k] % a[kk];
        }
      }
      for (int k = i; k < j; ++k) {
        vis[a[k]] = 1;
      }
      for (int k = 1; k <= N; ++k) {
        cnt[k] = vis[k] + cnt[k - 1];
        sum[k] = vis[k] * k + sum[k - 1];
      }
    }
    long long pp = 0;
    for (int i = 0; i < n; ++i) {
      pp += p[i];
      printf("%lld ", pp);
    }
    puts("");
    return 0;
  }
  