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