Ярослав играет в компьютерную игру, и на одном из уровней перед ним оказалось $$$n$$$ выстроенных в ряд грибов. Каждый гриб имеет свой уровень ядовитости, $$$i$$$-й с начала гриб имеет уровень ядовитости $$$a_i$$$. Ярослав может выбрать два целых числа $$$1 \le l \le r \le n$$$, а затем его персонаж будет по очереди слева направо поедать грибы из этого подотрезка, то есть грибы с номерами $$$l, l+1, l+2, \ldots, r$$$.
У персонажа есть уровень отравленности $$$g$$$, изначально равный $$$0$$$. Компьютерная игра определяется числом $$$x$$$ — максимальным уровнем отравленности в любой момент времени. При поедании гриба с ядовитостью $$$k$$$ происходит следующее:
Ярославу стало интересно, сколько существует способов выбрать значения $$$l$$$ и $$$r$$$ таких, что итоговое значение $$$g$$$ не равно нулю. Помогите Ярославу найти это число!
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \le x \le 10^9$$$) — количество грибов и максимальный уровень отравленности.
Вторая строка каждого набора входных данных содержит $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно число — количество подотрезков, таких что итоговое значение $$$g$$$ будет не равно нулю.
54 21 1 1 13 21 2 31 6106 31 2 1 4 3 85 999999999999999999 999999998 1000000000 1000000000 500000000
8 2 0 10 7
В первом наборе входных данных подходят подотрезки $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(3, 3)$$$, $$$(3, 4)$$$ и $$$(4, 4)$$$.
Во втором наборе входных данных ненулевое $$$g$$$ останется только на подотрезках $$$(1, 1)$$$ и $$$(2, 2)$$$.
В третьем наборе входных данных на единственном возможном подотрезке $$$g$$$ будет равно нулю.
Название |
---|