Задан массив \(a_1, a_2, \dots, a_n\), состоящий из \(n\) целых чисел. Также дано целое число \(x\).
Пусть \(f(k)\) будет равно максимальной сумме последовательного подмассива \(a\) после применения следующей операции: прибавить \(x\) к элементам на ровно \(k\) различных позициях. Пустой подмассив тоже рассматривается, его сумма равна \(0\).
Обратите внимание, что подмассив не обязан включать в себя все увеличенные элементы.
Посчитайте максимальное значение \(f(k)\) для каждого \(k\) от \(0\) до \(n\) независимо.
Выходные данные
На каждый набор входных данных выведите \(n + 1\) целое число — максимальное значение \(f(k)\) для каждого \(k\) от \(0\) до \(n\) независимо.
Примечание
В первом наборе не важно, к каким элементам прибавлять \(x\). Подотрезок с максимальной суммой всегда будет целым массивом. Если увеличить \(k\) элементов на \(x\), к сумме прибавится \(k \cdot x\).
Во втором наборе:
- Для \(k = 0\) пустой подмассив — это лучший вариант.
- Для \(k = 1\) наиболее выгодно увеличить элемент на позиции \(3\). Лучшая сумма становится \(-1 + 5 = 4\) для подмассива \([3, 3]\).
- Для \(k = 2\) наиболее выгодно увеличить элемент на позиции \(3\) и любой другой элемент. Лучшая сумма останется \(4\) для подотрезка \([3, 3]\).
- Для \(k = 3\) необходимо увеличить все элементы. Лучшая сумма становится \((-2 + 5) + (-7 + 5) + (-1 + 5) = 5\) для подотрезка \([1, 3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 2
4 1 3 2
3 5
-2 -7 -1
10 2
-6 -1 -2 4 -6 -1 -4 4 -5 -4
|
10 12 14 16 18
0 4 4 5
4 6 6 7 7 7 7 8 8 8 8
|