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.util.*;
  import java.io.*;
  
  public class Main {
      public static void main(String args[]) {new Main().run();}
  
      FastReader in = new FastReader();
      PrintWriter out = new PrintWriter(System.out);
      void run() {
          work();
          out.flush();
      }
      long mod=1000000007;
      long gcd(long a,long b) {
          return a==0?b:gcd(b%a,a);
      }
      int maxn=300005;
      long[] sum;
      long[] lazy;
      int n;
      void work() {
          n=ni();
          int[] A=nia(n);
          sum=new long[maxn<<2];
          lazy=new long[maxn<<2];
          long[] S=new long[maxn];
          long[] count=new long[maxn];
          long[] ret=new long[n];
          for(int i=0;i<n;i++){
              for(int j=0;j*A[i]<maxn;j++){
                  int s=A[i]*j,e=Math.min(A[i]*(j+1)-1,maxn-1);
                  long v=query(s,e,S);
                  long c=query(s,e,count);
                  ret[i]+=v-c*A[i]*j;
              }
              add(A[i],A[i],S);
              add(A[i],1,count);
          }
          for(int i=0;i<n;i++){
              ret[i]+=(long)i*A[i]-query(1,A[i],A[i],0,maxn);
              for(int j=0;j*A[i]<maxn;j++){
                  int s=A[i]*j,e=Math.min(A[i]*(j+1)-1,maxn-1);
                  add(1,s,e,A[i]*j,0,maxn);
              }
          }
          for(int i=1;i<n;i++){
              ret[i]+=ret[i-1];
          }
          for(long r:ret){
              out.print(r+" ");
          }
      }
  
      private long query(int node,int s, int e, int l, int r) {
          int m=(l+r)/2;
          push(node,l,r);
          if(s<=l&&r<=e){
              return sum[node];
          }
          long ret=0;
          if(s<=m){
              ret+=query(node<<1,s,e,l,m);
          }
          if(e>=m+1){
              ret+=query(node<<1|1,s,e,m+1,r);
          }
          return ret;
      }
  
      private void push(int node, int l, int r) {
          sum[node]+=lazy[node]*(r-l+1);
          if(l!=r){
              lazy[node<<1]+=lazy[node];
              lazy[node<<1|1]+=lazy[node];
          }
          lazy[node]=0;
      }
  
      private void add(int node,int s, int e, long v, int l, int r) {
          if(s<=l&&r<=e){
              lazy[node]+=v;
              return;
          }
          sum[node]+=(Math.min(r,e)-Math.max(s,l)+1)*v;
          int m=(l+r)/2;
          if(s<=m){
              add(node<<1,s,e,v,l,m);
          }
          if(e>=m+1){
              add(node<<1|1,s,e,v,m+1,r);
          }
      }
  
      int lowbit(int f){
          return f&-f;
      }
  
      long query(int s,int e,long[] B){
          return query(e,B)-query(s-1,B);
      }
  
      long query(int idx,long[] B){
          int n=B.length;
          long ret=0;
          for(;idx>0;idx-=lowbit(idx)){
              ret+=B[idx];
          }
          return ret;
      }
  
      private void add(int idx, long val, long[] B) {
          int n=B.length;
          for(;idx<n;idx+=lowbit(idx)){
              B[idx]+=val;
          }
      }
  
      //input
      @SuppressWarnings("unused")
      private ArrayList<Integer>[] ng(int n, int m) {
          ArrayList<Integer>[] graph=(ArrayList<Integer>[])new ArrayList[n];
          for(int i=0;i<n;i++) {
              graph[i]=new ArrayList<>();
          }
          for(int i=1;i<=m;i++) {
              int s=in.nextInt()-1,e=in.nextInt()-1;
              graph[s].add(e);
              graph[e].add(s);
          }
          return graph;
      }
  
      private ArrayList<long[]>[] ngw(int n, int m) {
          ArrayList<long[]>[] graph=(ArrayList<long[]>[])new ArrayList[n];
          for(int i=0;i<n;i++) {
              graph[i]=new ArrayList<>();
          }
          for(int i=1;i<=m;i++) {
              long s=in.nextLong()-1,e=in.nextLong()-1,w=in.nextLong();
              graph[(int)s].add(new long[] {e,w});
              graph[(int)e].add(new long[] {s,w});
          }
          return graph;
      }
  
      private int ni() {
          return in.nextInt();
      }
  
      private long nl() {
          return in.nextLong();
      }
      private double nd() {
          return in.nextDouble();
      }
      private String ns() {
          return in.next();
      }
  
      private long[] na(int n) {
          long[] A=new long[n];
          for(int i=0;i<n;i++) {
              A[i]=in.nextLong();
          }
          return A;
      }
  
      private int[] nia(int n) {
          int[] A=new int[n];
          for(int i=0;i<n;i++) {
              A[i]=in.nextInt();
          }
          return A;
      }
  }
  
  class FastReader
  {
      BufferedReader br;
      StringTokenizer st;
      InputStreamReader input;//no buffer
      public FastReader()
      {
          br=new BufferedReader(new InputStreamReader(System.in));
      }
  
      public FastReader(boolean isBuffer)
      {
          if(!isBuffer){
              input=new InputStreamReader(System.in);
          }else{
              br=new BufferedReader(new InputStreamReader(System.in));
          }
      }
  
      public boolean hasNext(){
          try{
              String s=br.readLine();
              if(s==null){
                  return  false;
              }
              st=new StringTokenizer(s);
          }catch(IOException e){
              e.printStackTrace();
          }
          return true;
      }
  
      public String next()
      {   
          if(input!=null){
              try {
                  StringBuilder sb=new StringBuilder();
                  int ch=input.read();
                  while(ch=='\n'||ch=='\r'||ch==32){
                      ch=input.read();
                  }
                  while(ch!='\n'&&ch!='\r'&&ch!=32){
                      sb.append((char)ch);
                      ch=input.read();
                  }
                  return sb.toString();
              }catch (Exception e){
                  e.printStackTrace();
              }
          }
          while(st==null || !st.hasMoreElements())//回车，空行情况
          {
              try {
                  st = new StringTokenizer(br.readLine());
              } catch (IOException e) {
                  e.printStackTrace();
              }
          }
          return st.nextToken();
      }
  
      public int nextInt()
      {
          return (int)nextLong();
      }
  
      public long nextLong() {
          try {
              if(input!=null){
                  long ret=0;
                  int b=input.read();
                  while(b<'0'||b>'9'){
                      b=input.read();
                  }
                  while(b>='0'&&b<='9'){
                      ret=ret*10+(b-'0');
                      b=input.read();
                  }
                  return ret;
              }
          }catch (Exception e){
              e.printStackTrace();
          }
          return Long.parseLong(next());
      }
  
      public double nextDouble()
      {
          return Double.parseDouble(next());
      }
  }