Задача ШАДа
Мощностью элемента массива назовем сумму максимального элемента, стоящего справа от него и максимального элемента стоящего от него слева.
Мощность крайних элементов будем считать равной 0.
У вас имеется первоначально пустой массив к которому по очереди справа приписываются n целых чисел. На каждом шаге посчитайте и выведите наибольшее значение среди мощностей его элементов.

В первом строке дается число n (1 <= n <= 10^6). Во второй строке дается сам массив.
Вывести n чисел - наибольшие мощности на каждом из n шагов.

Пример-1
3
1 4 5
Ответ 0 0 6
(если кто не понял объясню пример, вам сначала дают число 1, так как в списке у вас одно число то ответ 0, после вам дает число 4, так как всего у вас два числа то ответ 0, после вам дают число 5, можность для числа на второй позиции (4) будет равна 6, так как 1 + 5 = 6)

Пример-2
2 3 3 2
Ответ 0 0 5 5

Пример-3
6
6 5 4 3 2 1
Ответ 0 0 10 10 10 10

Решение:

Решим задача за O(N).
Предположим что вы уже получили i чисел, то есть у вас есть числа a[1], ..., a[i], вы знаете ответ для них равен ans[i].
Теперь вам дает i + 1 ое число, то есть a[i + 1].
В каких случаях ans[i + 1] может стать больше чем ans[i] ?
Очевидно чтобы это произошло в ans[i + 1] должен участвовать число a[i + 1] и какое-то максимальное число слева от позиции i (мы не можем взять число a[i] в ans[i + 1]) пусть это число max_pref, которую легко поддерижвать (смотрите код для лучшего понимания).
Таким образом получаем формулу:
ans[i] = max(ans[i - 1], a[i] + max_pref)

Код в комментариях.