Лена учится играть на пианино. У нее есть n композиций, упорядоченных по возрастанию сложности. Для каждой композиции Лена знает время, которое ей потребуется для ее исполнения. Перед тем, как начать учиться, она выбирает целое число L от 1 до n включительно и строит свою программу обучения следующим образом: в первый день она играет композиции 1 , 2 , . . . , L , во второй день композиции 2 , 3 , . . . , L + 1 и так далее. В день, когда Лена играет последнюю композицию, обучение заканчивается (действительно, она же успешно сыграла самую сложную композицию).
Лена заметила, что от выбора L время, которое она проведет за исполнением композиций, меняется. Ей стало интересно, сколько времени она проведет за исполнением композиций, если выберет L = 1 , 2 , . . . , n .
Требуется написать программу, которая для каждого L = 1 , 2 , . . . , n подсчитывает суммарное время, которое Лена потратит на исполнение композиций при заданном L .
Входные данные В первой строке записано число n ( 1 ≤ n ≤ 3 ⋅ 10 5 ) – количество композиций. В следующей строке через пробел записаны n чисел a 1 , a 2 , . . . , a n ( 1 ≤ a i ≤ 10 7 ) , где a i – время исполнения i -й композиции
Выходные данные Выведите n чисел через пробел – суммарное время для L = 1 , 2 , . . . , n соответственно.
Система оценки Решения, работающие правильно при n ≤ 5 , будут набирать не менее
Решения, работающие правильно при n ≤ 300 , будут набирать не менее
Решения, работающие правильно при n ≤ 10 000 , будут набирать не менее
Примеры входные данные 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 минут