F. Ямакаси
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ и два целых числа $$$s$$$ и $$$x$$$. Посчитайте количество подотрезков массива с суммой чисел, равной $$$s$$$, и максимальным значением, равным $$$x$$$.

Более формально, посчитайте количество пар $$$1 \leq l \leq r \leq n$$$ таких, что:

  • $$$a_l + a_{l + 1} + \ldots + a_r = s$$$.
  • $$$\max(a_l, a_{l + 1}, \ldots, a_r) = x$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$s$$$ и $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$-2 \cdot 10^{14} \leq s \leq 2 \cdot 10^{14}$$$, $$$-10^9 \leq x \leq 10^9$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите количество подотрезков массива с суммой чисел, равной $$$s$$$, и максимальным значением, равным $$$x$$$.

Пример
Входные данные
9
1 0 0
0
1 -2 -1
-2
3 -1 -1
-1 1 -1
6 -3 -2
-1 -1 -1 -2 -1 -1
8 3 2
2 2 -1 -2 3 -1 2 2
9 6 3
1 2 3 1 2 3 1 2 3
13 7 3
0 -1 3 3 3 -2 1 2 2 3 -1 0 3
2 -2 -1
-2 -1
2 -2 -1
-1 -2
Выходные данные
1
0
2
0
2
7
8
0
0
Примечание

В первом наборе входных данных подходит подотрезок $$$l = 1$$$, $$$r = 1$$$.

В третьем наборе входных данных подходят подотрезки $$$l = 1$$$, $$$r = 1$$$ и $$$l = 3$$$, $$$r = 3$$$.

В пятом наборе входных данных подходят подотрезки $$$l = 1$$$, $$$r = 3$$$ и $$$l = 6$$$, $$$r = 8$$$.

В шестом наборе входных данных подходят подотрезки, для которых $$$r = l + 2$$$.

В седьмом наборе входных данных подходят следующие подотрезки:

  • $$$l = 1$$$, $$$r = 7$$$.
  • $$$l = 2$$$, $$$r = 7$$$.
  • $$$l = 3$$$, $$$r = 6$$$.
  • $$$l = 4$$$, $$$r = 8$$$.
  • $$$l = 7$$$, $$$r = 11$$$.
  • $$$l = 7$$$, $$$r = 12$$$.
  • $$$l = 8$$$, $$$r = 10$$$.
  • $$$l = 9$$$, $$$r = 13$$$.