|
Пусть
S
– последовательность из
N
целых чисел, пронумерованных подряд начиная с 1.
Обозначим
S
(
L
,
R
) подпоследовательность, состоящую из идущих подряд элементов, входящих в
S
, начиная с элемента с номером
L
и заканчивая элементом с номером
R
включительно.
Требуется найти такую подпоследовательность
S
(
L
,
R
) максимальной длины, что сумма её элементов отрицательна и нечётна. Гарантируется, что хотя бы одна подпоследовательность требуемого вида существует.
В ответе укажите длину искомой подпоследовательности.
Входные данные
Дано два входных файла (файл
A
и файл
B
), каждый из которых в первой строке
содержит число
N
(5 ≤
N
≤ 10 000 000) – количество
целых чисел
. Каждая из следующих
N
строк содержит одно целое число, значение которого по модулю не превышает
1000
.
В ответе
укажите два числа: сначала значение искомой величины для файла
А
, затем – для файла
B
.
Типовой пример организации данных во входном файле
6
20
2
–8
4
–5
3
При таких входных данных
L
= 2,
R
= 5. Сумма подпоследовательности равна (2 + (–8) + 4 + (–5)) = –7
.
Ответом является длина этой подпоследовательности, равная 4.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение:
для обработки файла
B
не следует
использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
|