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: import java.io.*;
  import java.util.*;
  
  public class Main {
  
      public static int MAX = 300009;
      public static long[] c = new long[MAX];
      public static long[] s = new long[MAX];
      public static long[][] segtree = new  long[4 * MAX][2];
  
      public static void update(int v, int l, int r, int tl, int tr, int x) {
          if (l > tr || r < tl || l > r || tl > tr) return;
          if (l == tl && r == tr) {
              segtree[v][0] += x;
              segtree[v][1] += 1;
          } else {
              int m = (l + r) / 2;
              update(v * 2 + 1, l, m, tl, Math.min(m, tr), x);
              update(v * 2 + 2, m + 1, r, Math.max(tl, m + 1), tr, x + Math.max(tl, m + 1) - tl);
          }
      }
  
      public static long sum(int v, int l, int r, int pos) {
          if (l > r) return 0;
          if (l == r){
              return segtree[v][0];
          }
          long ans = 0;
          int m = (l + r) / 2;
          if (pos <= m){
              ans += sum(v * 2 + 1, l, m, pos);
          } else {
              ans += sum(v * 2 + 2, m + 1, r, pos);
          }
          ans += segtree[v][0] + (pos - l) * segtree[v][1];
          return ans;
      }
  
      public static long sum(int r, long[] t) {
          long result = 0;
          if (r >= MAX) r = MAX - 1;
          for (; r >= 0; r = (r & (r + 1)) - 1)
              result += t[r];
          return result;
      }
  
      public static void inc(int i, long delta, long[] t) {
          int n = t.length;
          if (i >= n) return;
          for (; i < n; i = (i | (i + 1)))
              t[i] += delta;
      }
  
      public static long sum(int l, int r, long[] t) {
          return sum(r, t) - sum(l - 1, t);
      }
  
      public static void main(String[] args) throws Exception {
          int n = r.readInt();
          int[] a = r.readIntArray(n);
          long[] p = new long[n];
          for (int i = 1; i < n; i++) {
              inc(a[i - 1], 1, c);
              inc(a[i - 1], a[i - 1], s);
              for (int j = a[i - 1]; j < MAX; j += a[i - 1]) {
                  update(0, 0, MAX, j + 1, Math.min(j + a[i - 1] - 1, MAX), 1);
              }
  
              p[i] = p[i - 1];
  
              // a[j] % a[i]
              p[i] += sum(0, a[i] - 1, s);
              for (int j = a[i]; j < MAX; j += a[i]) {
                  p[i] += sum(j, j + a[i] - 1, s) - j * sum(j, j + a[i] - 1, c);
              }
  
              // a[i] % a[j]
              p[i] += sum(a[i] + 1, MAX, c) * a[i];
              p[i] += sum(0, 0, MAX, a[i]);
          }
  
          for (int i = 0; i < n; i++) {
              w.writer.print(p[i] + " ");
          }
          w.writer.flush();
      }
  
      static public InputReader r = new InputReader(System.in);
      static public OutputWriter w = new OutputWriter(System.out);
  
      static public class InputReader {
          private InputStream stream;
          private byte[] buf = new byte[1024];
          private int curChar;
          private int numChars;
          private InputReader.SpaceCharFilter filter;
  
          public InputReader(InputStream stream) {
              this.stream = stream;
          }
  
          public int read() {
              if (numChars == -1)
                  throw new InputMismatchException();
              if (curChar >= numChars) {
                  curChar = 0;
                  try {
                      numChars = stream.read(buf);
                  } catch (IOException e) {
                      throw new InputMismatchException();
                  }
                  if (numChars <= 0)
                      return -1;
              }
              return buf[curChar++];
          }
  
          public int readInt() {
              int c = read();
              while (isSpaceChar(c))
                  c = read();
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              int res = 0;
              do {
                  if (c < '0' || c > '9')
                      throw new InputMismatchException();
                  res *= 10;
                  res += c - '0';
                  c = read();
              } while (!isSpaceChar(c));
              return res * sgn;
          }
  
          public int[] readIntArray(int n) {
              int[] array = new int[n];
              for (int i = 0; i < n; i++) {
                  array[i] = this.readInt();
              }
              return array;
          }
  
          public long[] readLongArray(int n) {
              long[] array = new long[n];
              for (int i = 0; i < n; i++) {
                  array[i] = this.readLong();
              }
              return array;
          }
  
          public long readLong() {
              int c = read();
              while (isSpaceChar(c))
                  c = read();
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              long res = 0;
              do {
                  if (c < '0' || c > '9')
                      throw new InputMismatchException();
                  res *= 10;
                  res += c - '0';
                  c = read();
              } while (!isSpaceChar(c));
              return res * sgn;
          }
  
          public String readString() {
              int c = read();
              while (isSpaceChar(c))
                  c = read();
              StringBuilder res = new StringBuilder();
              do {
                  res.appendCodePoint(c);
                  c = read();
              } while (!isSpaceChar(c));
              return res.toString();
          }
  
          public boolean isSpaceChar(int c) {
              if (filter != null)
                  return filter.isSpaceChar(c);
              return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
          }
  
          public String next() {
              return readString();
          }
  
          public interface SpaceCharFilter {
              public boolean isSpaceChar(int ch);
          }
      }
  
      static public class OutputWriter {
          private final PrintWriter writer;
  
          public OutputWriter(OutputStream outputStream) {
              writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
          }
  
          public OutputWriter(Writer writer) {
              this.writer = new PrintWriter(writer);
          }
  
          public void print(Object... objects) {
              for (int i = 0; i < objects.length; i++) {
                  if (i != 0)
                      writer.print(' ');
                  writer.print(objects[i]);
              }
          }
  
          public void printLine(Object... objects) {
              print(objects);
              writer.println();
          }
  
          public void close() {
              writer.close();
          }
      }
  }