CF2149E Hidden Knowledge of the Ancients

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 $ .

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 $ .

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

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 $ .