Дистанционный практикум по программированию

Предприниматель Сигизмунд хранит сведения о прибыли своей фирмы за каждый день её работы с момента основания. Однако, дела в его компании идут не слишком хорошо, поэтому в некоторые дни прибыль может оказаться отрицательной.

Для поднятия настроения Сигизмунд решил найти самый длинный интервал времени, в котором суммарная прибыль была положительна. Помогите ему это сделать.

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

В первой строке входных данных записано натуральное число N – количество дней (1 ≤ N ≤ 10⁵).

В следующей строке записаны через пробел N целых чисел p₁, p₂, ..., p_N – прибыль компании в день 1, 2, ..., N ( -10⁶ ≤ p_i ≤ 10⁶).

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

Выведите одно натуральное число – максимальную длину найденного интервала, на котором суммарная прибыль больше нуля.

Примечание.  В примере из условия положительная прибыль получилась на интервале длиной 5 дней, начиная с третьего дня: (-1) + 2 + (-3) + 2 + 3 = 3.

Система оценивания.

Подзадача 1 (30 баллов):  N ≤ 100

Подзадача 2 (30 баллов):  N ≤ 1000

Подзадача 3 (40 баллов):  N ≤ 10⁵

Во всех подзадачах баллы даются, только если все тесты этой подзадачи пройдены.