В файле представлена замкнутая последовательность натуральных чисел, не превышающих 10_000. Первый элемент последовательности можно считатть следующим после последнего элемента, Например, последовательности 1, 2, 3, 4, 5 и 2, 3, 4,. 5, 1 описывают одну и ту же замкнутую последовательность. Назовём хорошей последовательность длиной не менее 2, в которой сумма всех значений кратна сумме первого и последнего элементов этой последовательности. Например, последовательность 2, 3, 4, 5, 2 хорошая, так как 2+3+4+5+2 = 16 кратна 2+2 = 4.
Нужно разделить всю последовательность на две хорошие подпоследовательности. В ответе надо указать сумму четырёх чисел: два числа (первое и последнее) в первой хорошей подпоследовательности, два числа (первое и последнее) во второй хорошей подпоследовательности. Если вариантов разделения несколько, приведите максимальное значение суммы (в подпоследовательности не может быть менее двух чисел).
Входные данные
В первой строке записано число n (4 <= n <= 50000) - количество элементов в замкнутой последовательности. В следующих n строках по порядку записано по одному числу последовательности.
Выходные данные
Одно число для каждого файла - сумма 4 чисел.
Пример входных данных
7
1
5
2
9
4
2
6
Данную последовательность можно разделить на две подпоследоввательности двумя способами:
[2, 9] и [4, 2, 6, 1, 5] 2+9+4+5 = 20
[9, 4] и [2, 6, 1, 5, 2] 9+ 4 + 2 + 2 = 17
Ответ 20
Файл А Файл В