Максимальная разность сумм

Задание выполняется с использованием прилагаемых
файлов.

Пусть S – последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L, R) подпоследовательность, состоящую из идущих подряд элементов, входящих в S, начиная с элемента с номером L и заканчивая элементом с номером R.

Требуется найти такие значения номеров элементов L, M, R, где
0 < L < M < R – 1 (т.е. между элементами с номерами M и R есть ещё как минимум один элемент), чтобы разность суммы элементов подпоследовательности S(M + 1, R) и суммы элементов подпоследовательности S(L, M) была максимальна.

В ответе укажите максимальное значение разности подобных сумм.

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

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

В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

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

7

20

4

–2

13

–1

2

–10

При таких входных данных L = 2, M = 3, R = 6. Искомая максимальная разность равна (13 + (–1) + 2) – (4 + (–2)) = 12. Подпоследовательность «–2 13 –1» разбить на две подпоследовательности требуемого вида невозможно.

Ответом является число 12.

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

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