E. Hidden Knowledge of the Ancients
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the world of Deepwoken, there exists an ancient artifact — Tablet of Infinite Knowledge, on which a sequence of $$$n$$$ mysterious symbols (each symbol is an integer) is engraved.

It is said that the true power of the artifact can only be revealed by finding all sacred fragments — continuous segments of the tablet that contain exactly $$$k$$$ distinct numbers, and their length must be between $$$l$$$ and $$$r$$$ (inclusive).

Formally: Given a sequence $$$a$$$ of length $$$n$$$ and integers $$$k$$$, $$$l$$$, $$$r$$$. You need to find the number of such boundaries $$$b$$$ and $$$c$$$ such that:

  • $$$1 \le b \le c \le n$$$;
  • among the elements [$$$a_{b}, a_{b + 1}, \dots, a_{c}$$$] there are exactly $$$k$$$ distinct numbers;
  • $$$l \leq c - b + 1 \leq r$$$.
Input

Each test consists of several test cases.

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The following describes the test cases.

The first line of each test case contains four integers: $$$n$$$, $$$k$$$, $$$l$$$, and $$$r$$$ $$$( 1 \le k \le n \le 2 \cdot 10^5, 1 \le l \le r \le n)$$$.

The second line contains $$$n$$$ numbers $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — the mysterious symbols.

It is guaranteed that the total value of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test, output a single integer on a separate line — the number of continuous subarrays that meet the specified conditions.

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

In the first test case $$$a=[5]$$$, there is only one subarray $$$[5]$$$, which has a length of 1 and contains exactly $$$1$$$ distinct number.

In the fourth test case $$$a=[7,7,7,7]$$$, any subarray of identical numbers gives exactly $$$1$$$ distinct number. The start and end of possible subarrays are:

  • Length $$$1$$$: $$$[1,1]$$$, $$$[2,2]$$$, $$$[3,3]$$$, $$$[4,4]$$$.
  • Length $$$2$$$: $$$[1,2]$$$, $$$[2,3]$$$, $$$[3,4]$$$.
In total: $$$7$$$.

In the fifth test case $$$a=[1,2,1,2,3,2,1]$$$:

  • Length $$$2$$$: all subarrays have only $$$2$$$ distinct numbers.
  • Length $$$3$$$: $$$[3,5]$$$, $$$[5,7]$$$.
  • Length $$$4$$$: $$$[2,5]$$$, $$$[3,6]$$$, $$$[4,7]$$$.
In total: $$$5$$$.