Задача №112836. Максимум
Назовем фрагментом числовой последовательности любую ее непустую подпоследовательность без пропусков. Например, фрагментами последовательности чисел 1, 7, 3 есть сама последовательность 1 , 7 , 3 , ее двухэлементные подпоследовательности 1 , 7 и 7 , 3 (но не подпоследовательность 1 , 3 ), а также три одноэлементные подпоследовательности 1 , 7 и 3 . Напишите программу maximum, которая для последовательности чисел и величины M определит, сколько существует фрагментов заданной последовательности, максимум на которых равен M . Фрагменты, содержащие одинаковые числа, но располагающиеся в разных местах последовательности, мы считаем разными.
В первой строке входного файла записаны два натуральных числа: N (2 ≤ N ≤ 10 5 ) — длина последовательности чисел — и M (1 ≤ M ≤ 10 9 ) . Во второй строке содержится последовательность из N натуральных чисел, каждое из которых не превышает 10 9 .
Выходной файл должен содержать единственное число — количество фрагментов последовательности, наибольшее число которых равно M .
Набор тестов состоит из 3 блоков, для которых дополнительно выполняются такие условия:
-
20 баллов:
2 ≤
N
≤ 100
-
20 баллов:
100 <
N
≤ 1000
-
30 баллов:
1000 <
N
≤ 10
5
4 5 1 5 1 2
6
2 2 3 4
0