a27_0098

Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(P, K) подпоследовательность, состоящую из не менее чем двух идущих подряд элементов, входящих в S, начиная с элемента с номером P и заканчивая элементом с номером K, где 0 < Р < К.

Определите две такие непересекающиеся подпоследовательности S(L, Q) и S(R, Т), между которыми находится по крайней мере один элемент, т.е. Q < R - 1, чтобы сумма всех их элементов была максимальна. В ответе запишите абсолютное значение найденной максимальной суммы.

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

Дано два входных файла (файл А и файл В), каждый из которых в первой строке содержит число N (5 < N< 10 000 000) — количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000. В ответе укажите два числа: сначала значение искомой величины для файла А, затем — для файла В.

Типовой пример организации данных во входном файле

6
-1
5
3
-4
2
-10

При таких входных данных искомую максимальную сумму, равную двум, образуют суммы всех элементов подпоследовательностей
S(1, 2) и S(4, 5). Ответом на вопрос задачи является число 2.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

**Предупреждение:**для обработки файла В не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Файлы к заданию:

• a27_0098A.txt
• a27_0098B.txt