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