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
import java.util.*;
import java.io.*;

public class F1553 {
	static final int SIZE = (int) 3e5 + 5;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		int n = sc.nextInt();
		int[] arr = sc.nextIntArr(n);
		FenwickTree sum = new FenwickTree(SIZE);
		FenwickTree cnt = new FenwickTree(SIZE);
		FenwickTree rep = new FenwickTree(SIZE);
		long ans = 0;
		for (int x : arr) {
			ans += x == 1 ? 0 : sum.rsq(x - 1);
			ans += 1l * cnt.rsq(x, SIZE) * x;
			ans += x == 1 ? 0 : 1l * x * cnt.rsq(x - 1);
			ans -= rep.rsq(x);
			ans += sum.rsq(x, SIZE);
			int l = x;
			int r = 2 * x - 1;
			long w = 1;

			while (l < SIZE) {
				ans -= 1l * cnt.rsq(l, r) * w * x;
				rep.point_update(l, x);
				r += x;
				l += x;
				w++;
			}
			cnt.point_update(x, 1);
			sum.point_update(x, x);
			pw.print(ans + " ");
		}
		pw.println();
		pw.close();
	}

	static class FenwickTree { // one-based DS

		int n;
		long[] ft;

		FenwickTree(int size) {
			n = size;
			ft = new long[n + 1];
		}

		long rsq(int b) // O(log n)
		{
			long sum = 0;
			while (b > 0) {
				sum += ft[b];
				b -= b & -b;
			} // min?
			return sum;
		}

		long rsq(int a, int b) {
			b = Math.min(b, SIZE - 1);
			return rsq(b) - rsq(a - 1);
		}

		void point_update(int k, long val) // O(log n), update = increment
		{
			while (k <= n) {
				ft[k] += val;
				k += k & -k;
			} // min?
		}
	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader f) {
			br = new BufferedReader(f);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArr(int n) throws IOException {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(next());
			}
			return arr;
		}

	}

}
