E. Hidden Knowledge of the Ancientstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputIn 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$$$. InputEach 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$$$.OutputFor each test, output a single integer on a separate line — the number of continuous subarrays that meet the specified conditions.ExampleInput51 1 1 155 2 2 31 2 1 3 26 3 1 61 2 3 1 2 34 1 1 27 7 7 77 3 2 41 2 1 2 3 2 1Output151075NoteIn 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$$$.