По каналу связи передаётся последовательность целых неотрицательных чисел – показания прибора, полученные с интервалом в 1 мин. в течение T мин. (T – целое число). Прибор измеряет количество атмосферных осадков, полученное регистратором за минуту, предшествующую моменту регистрации, и передаёт это значение в условных единицах измерения.

Ученые анализируют последовательность и выявляют смежные диапазоны времени, содержащие не менее K измерений каждый, в которые выпало одинаковое количество осадков.

Определите, сколько таких смежных пар диапазонов есть в снятой последовательности.

в первой строке содержит натуральное число K – минимальное количество показаний в каждом из смежных диапазонов, а во второй – количество переданных показаний N (1 ≤ N ≤ 10 000, N >> K). В каждой из следующих N строк находится одно целое неотрицательное число, не превышающее 1000, обозначающее количество осадков за соответствующую минуту.

Пример данных:
2
8
1
2
3
4
1
1
2
5
При таких исходных данных количество смежных периодов с одинаковым количеством осадков 4: ((2, 3), (4, 1)), ((1, 2, 3), (4, 1, 1)), ((3, 4, 1), (1, 2, 5)), ((2, 3, 4), (1, 1, 2, 5)).

Пока мысли насчитать префиксных сумм и использовать их. Но эффективного алгоритма не придумывается что то.