Вам дан массив, состоящий из n неотрицательных целых чисел a1, a2, ..., an.
В этом массиве один за другим зачёркиваются числа. Вам задана перестановка чисел от 1 до n — порядок, в котором это происходит.
После зачёркивания очередного числа вам необходимо найти в этом массиве подотрезок с максимальной суммой, не содержащий ни одного зачёркнутого числа. Сумму чисел в пустом подотрезке считайте равной 0.
Выходные данные
В выходной файл выведите n строк, каждая из которых должна содержать одно число — максимальную сумму на подотрезке заданного массива, не содержащем зачёркнутых чисел, после выполнения очередного действия.
Примечание
В первом тестовом примере происходит следующее:
- Зачеркивается третий элемент, массив принимает вид 1 3 * 5. Отрезок с максимально суммой 5 состоит из одного числа 5.
- Зачеркивается четвертый элемент, массив принимает вид 1 3 * * . Отрезок с максимально суммой 4 состоит из двух чисел 1 3.
- Зачеркивается первый элемент, массив принимает вид * 3 * * . Отрезок с максимально суммой 3 состоит из одного числа 3.
- Зачеркивается оставшийся второй элемент, в этот момент непустых допустимых подотрезков не остается, поэтому здесь ответ равен нулю.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 3 2 5
3 4 1 2
|
5
4
3
0
|
|
2
|
5
1 2 3 4 5
4 2 3 5 1
|
6
5
5
1
0
|
|
3
|
8
5 5 4 4 6 6 5 5
5 2 8 7 1 3 4 6
|
18
16
11
8
8
6
6
0
|