Белые медведи Меньшиков и Услада из Санкт-Петербургского зоопарка и слоник Хорас из Киевского зоопарка где-то достали очень много деревянных кубиков. Из кубиков они стали строить башенки, ставя кубики один на другой, а башенки, поставленные в ряд, назвали стенкой. Стенка может состоять из башенок различных высот.
Хорас первым закончил собирать свою стенку и назвал ее слоном, эта стенка состоит из w башенок. Медведи тоже закончили собирать свою стенку, но никак ее не назвали. Их стенка состоит из n башенок. Хорас посмотрел на стенку медведей, и его заинтересовало, в скольких участках этой стенки он может «увидеть слона». «Увидеть слона» можно на участке из w последовательных башенок, если высоты башенок на участке как последовательность совпадают с высотами башенок в стенке Хораса. Чтобы увидеть больше слонов Хорас может поднимать или опускать всю свою стенку целиком, в том числе Хорас может опустить свою стенку ниже уровня пола (посмотрите рисунки к тестовым примерам для лучшего понимая).
От вас требуется посчитать количество участков, на которых можно «увидеть слона».
Выходные данные
Выведите количество участков в стенке медведей, на которых можно «увидеть слона».
Примечание
Слева на иллюстрации изображена стенка Хораса из примера, справа — стенка медведей. Серым цветом выделены места, в которых можно «увидеть слона».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
13 5
2 4 5 5 4 3 2 2 2 3 3 2 1
3 4 4 3 2
|
2
|