№ 5 Пусть 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 не следует использовать переборный алгоритм, вычисляющий разность для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

№ 6 Пусть S – последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три элемента последовательности S, где i < j < k.

Определите в последовательности S три таких числа Si, Sj, Sk, что Si > Sj, Sk > Sj и значение выражения (Si – Sj) + (Sk – Sj) максимально. В ответе укажите найденное максимальное значение выражения (Si – Sj) + (Sk – Sj). Гарантируется, что в последовательности есть три числа Si, Sj, Sk, удовлетворяющие условию задачи.

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

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

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

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

9
6
9
7
5
8
6
10
–5
–6

При таких входных данных искомую максимальную сумму разностей образуют второй, четвёртый и седьмой элементы данной последовательности. Значение этой суммы разностей равно (9 – 5) + (10 – 5) = 9. Для седьмого, восьмого и девятого элементов последовательности искомая величина равна 14, но девятый элемент меньше восьмого, что не удовлетворяет условию задачи. Ответом является число 9.

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

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