G. Monkey Arrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yash really likes monkeys and special arrays. Because he was curious, Curios George gave Yash an array $$$A$$$ of length $$$N$$$, and now Yash wonders how many good subarrays exist in this array.

Specifically, Yash deems a subarray good if $$$X$$$, his favorite number, is the maximum value in the subarray, $$$Y$$$, his second favorite number, is the minimum in the subarray, and $$$K$$$, his least favorite number, is not in the subarray. In other words, in a given subarray, $$$X$$$ should be the maximum value, $$$Y$$$ should be the minimum, and $$$K$$$ should not be in the subarray.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ $$$(1 \leq t \leq 5 \cdot 10^4)$$$ — the number of test cases.

The first line of each test case contains four integers $$$N$$$, $$$X$$$, $$$Y$$$, and $$$K$$$ ($$$1 \le N \le 5 \cdot 10^5, 1 \le Y \lt K \lt X \le 10^9$$$).

The second line of each test case contains $$$N$$$ integers $$$A_1,A_2,\ldots,A_N$$$ ($$$1 \le A_i \le 10^9$$$) — the elements of the array $$$A$$$.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-5$$$ satisfy that the sum of $$$N$$$ over all test cases does not exceed $$$100$$$.

Tests $$$6-10$$$ satisfy that the sum of $$$N$$$ over all test cases does not exceed $$$1000$$$.

The remaining tests do not satisfy any additional constraints.

Output

For each test case, output a single integer — the number of good subarrays in the array $$$A$$$.

Example
Input
3
8 7 4 5
6 7 4 6 5 4 6 7
6 5 2 4
3 2 4 5 1 3
12 8 3 6
10 4 3 7 4 8 6 5 1 3 8 2
Output
5
0
3
Note

In the first test case of the sample test, the $$$5$$$ subarrays that are good are $$$[6, 7, 4]$$$, $$$[6, 7, 4, 6]$$$, $$$[7, 4]$$$, $$$[7, 4, 6]$$$, and $$$[4, 6, 7]$$$.

In the second test case of the sample test, there are no good subarrays.

—

Problem Idea: yash_9a3b

Problem Preparation: yash_9a3b, xug

Occurrences: Novice G, Advanced B