Дана последовательность из
N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна
k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Входные данные
Даны два входных файла (
файл A и
файл B), каждый из которых содержит в первой строке количество чисел
N (1<= N <= 10 000 000). Каждая из следующих
N строк содержит одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
7
21
13
9
19
17
26
95
В этом наборе можно выбрать последовательности
21+13+9 (сумма
43) и
17+26 (сумма
43). Самая короткая из них,
17 + 26, имеет длину
2. Для указанных программа должна вывести число
2.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.