CF2121F Yamakasi

You are given an array of integers $ a_1, a_2, \ldots, a_n $ and two integers $ s $ and $ x $ . Count the number of subsegments of the array whose sum of elements equals $ s $ and whose maximum value equals $ x $ . More formally, count the number of pairs $ 1 \leq l \leq r \leq n $ such that: - $ a_l + a_{l + 1} + \ldots + a_r = s $ . - $ \max(a_l, a_{l + 1}, \ldots, a_r) = x $ .

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains three integers $ n $ , $ s $ , and $ 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 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^9 \leq a_i \leq 10^9 $ ). It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output the number of subsegments of the array whose sum of elements equals $ s $ and whose maximum value equals $ x $ .

In the first test case, the suitable subsegment is $ l = 1 $ , $ r = 1 $ . In the third test case, the suitable subsegments are $ l = 1 $ , $ r = 1 $ and $ l = 3 $ , $ r = 3 $ . In the fifth test case, the suitable subsegments are $ l = 1 $ , $ r = 3 $ and $ l = 6 $ , $ r = 8 $ . In the sixth test case, the suitable subsegments are those for which $ r = l + 2 $ . In the seventh test case, the following subsegments are suitable: - $ 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 $ .