F. Попарные остатки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a$$$, состоящий из $$$n$$$ различных положительных целых чисел, пронумерованных от $$$1$$$ до $$$n$$$. Определим $$$p_k$$$ как $$$$$$p_k = \sum_{1 \le i, j \le k} a_i \bmod a_j,$$$$$$

где $$$x \bmod y$$$ обозначает остаток при делении $$$x$$$ на $$$y$$$. От вас требуется найти и вывести $$$p_1, p_2, \ldots, p_n$$$.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длину массива.

Вторая строка содержит $$$n$$$ различных целых чисел $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 3 \cdot 10^5$$$, $$$a_i \neq a_j$$$, если $$$i \neq j$$$).

Выходные данные

Выведите $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$.

Примеры
Входные данные
4
6 2 7 3
Выходные данные
0 2 12 22
Входные данные
3
3 2 1
Выходные данные
0 3 5