D. Уроки музыки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лена учится играть на пианино. У нее есть $$$n$$$ композиций, упорядоченных по возрастанию сложности. Для каждой композиции Лена знает время, которое ей потребуется для ее исполнения. Перед тем, как начать учиться, она выбирает целое число $$$L$$$ от 1 до $$$n$$$ включительно и строит свою программу обучения следующим образом: в первый день она играет композиции $$$1,\:2,\:...,\:L$$$, во второй день композиции $$$2,\:3,\:...,\:L+1$$$ и так далее. В день, когда Лена играет последнюю композицию, обучение заканчивается (действительно, она же успешно сыграла самую сложную композицию).

Лена заметила, что от выбора $$$L$$$ время, которое она проведет за исполнением композиций, меняется. Ей стало интересно, сколько времени она проведет за исполнением композиций, если выберет $$$L=1,\:2,\:...,\:n$$$.

Требуется написать программу, которая для каждого $$$L = 1, 2, ..., n$$$ подсчитывает суммарное время, которое Лена потратит на исполнение композиций при заданном $$$L$$$.

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

В первой строке записано число $$$n\:(1 \le n \le 3 \cdot 10^5)$$$ – количество композиций. В следующей строке через пробел записаны $$$n$$$ чисел $$$a_1,\: a_2,\:...,\:a_n\:(1 \le a_i \le 10^7)$$$, где $$$a_i$$$ – время исполнения $$$i$$$-й композиции

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

Выведите $$$n$$$ чисел через пробел – суммарное время для $$$L=1,\:2,\:...,\:n$$$ соответственно.

Система оценки

Решения, работающие правильно при $$$n \le 5$$$, будут набирать не менее 20 баллов

Решения, работающие правильно при $$$n \le 300$$$, будут набирать не менее 35 баллов

Решения, работающие правильно при $$$n \le 10\:000$$$, будут набирать не менее 60 баллов

Примеры
Входные данные
4
1 3 2 4
Выходные данные
10 15 15 10
Входные данные
5
5 1 3 5 4
Выходные данные
18 27 30 27 18
Примечание

Обращаем ваше внимание на то, что ответ в данной задаче может быть достаточно большим, поэтому рекомендуем использовать 64-битный тип данных. В C++ для этого предусмотрен тип long long, в Pascal – int64.

Так же, давайте разберем первый пример из условия:

При $$$L=1$$$

В первый день Лена потратит 1 минуту

Во второй – 3 минуты

В третий – 2 минуты

И в четвертый – 4 минуты

Итого 1+3+2+4=10 минут

При $$$L=2$$$

В первый день Лена потратит 1+3=4 минуты

Во второй – 3+2=5 минут

В третий – 2+4=6 минут и закончит обучение, так как сыграет последнюю композицию

Итого 4+5+6=15 минут

При $$$L=3$$$

В первый день Лена потратит 1+3+2=6 минут

Во второй – 3+2+4=9 минут

Итого 6+9=15 минут

При $$$L=4$$$

В первый и единственный день Лена потратит 1+2+3+4=10 минут