1553_F. Pairwise Modulo_103
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
from sys import stdin, stdout


def bit_update(bit_a, i, v):
    while i < len(bit_a):
        bit_a[i] += v

        i += (i & -i)


def bit_query(bit_a, i):
    r = 0
    while i > 0:
        r += bit_a[i]

        i -= (i & -i)
    return r


def bit_range_query(bit_a, l, r):
    return bit_query(bit_a, r) - bit_query(bit_a, l-1)


n = int(stdin.readline())
a_a = list(map(int, stdin.readline().split()))

N = max(a_a) + 1
bit_a = [0 for _ in range(N*2)]
bit_a2 = [0 for _ in range(N*2)]
p_a = [0] * n
ans = sum = 0
# 1 2 3 | 10 => 3*10 - (1*10 + 2*5 + 3*3)
# 12 22 | 10 => 12-10 + 22-20
for i in range(1, n+1):
    x = a_a[i-1]
    ans += x * (i-1)
    ans += sum
    sum += x
    ans -= bit_query(bit_a, x)

    j = x
    while j < N:
        l = j
        r = l+x-1
        ans -= bit_range_query(bit_a2, l, r) * j
        bit_update(bit_a, l, x)
        j += x
    bit_update(bit_a2, x, 1)

    p_a[i-1] = ans

stdout.write(' '.join(map(str, p_a)))
