E. Скрытые знания древних
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В мире Deepwoken существует древний артефакт — Табличка Бесконечного Знания, на которой выгравирована последовательность из $$$n$$$ загадочных символов (каждый символ — целое число).

Говорят, что истинную силу артефакта можно раскрыть, только если найти все священные фрагменты — непрерывные участки таблички, содержащие ровно $$$k$$$ различных чисел, причём их длина должна быть от $$$l$$$ до $$$r$$$ (включительно).

Формально: Дана последовательность $$$a$$$ длины $$$n$$$ и целые числа $$$k$$$, $$$l$$$, $$$r$$$. Необходимо найти количество таких границ $$$b$$$ и $$$c$$$, что:

  • $$$1 \le b \le c \le n$$$;
  • среди элементов [$$$a_{b}, a_{b + 1}, \dots, a_{c}$$$] ровно $$$k$$$ различных чисел;
  • $$$l \leq c - b + 1 \leq r$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных.

В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит четыре целых числа: $$$n$$$, $$$k$$$, $$$l$$$ и $$$r$$$ $$$( 1 \le k \le n \le 2 \cdot 10^5, 1 \le l \le r \le n)$$$.

Во второй строке задано $$$n$$$ чисел $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — загадочные символы.

Гарантируется, что суммарное значение $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке одно целое число — количество непрерывных подмассивов, которые соответствуют указанным условиям.

Пример
Входные данные
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
Выходные данные
1
5
10
7
5
Примечание

В первом наборе входных данных $$$a=[5]$$$ есть всего один подмассив $$$[5]$$$, он длины 1 и содержит ровно $$$1$$$ различное число.

В четвёртом наборе входных данных $$$a=[7,7,7,7]$$$ любой подмассив из одинаковых чисел даёт ровно $$$1$$$ различное число. Начало и конец возможных подмассивов:

  • Длина $$$1$$$: $$$[1,1]$$$, $$$[2,2]$$$, $$$[3,3]$$$, $$$[4,4]$$$.
  • Длина $$$2$$$: $$$[1,2]$$$, $$$[2,3]$$$, $$$[3,4]$$$.
Итого: $$$7$$$.

В пятом наборе входных данных $$$a=[1,2,1,2,3,2,1]$$$:

  • Длина $$$2$$$: все подмассивы имеют только $$$2$$$ различных числа.
  • Длина $$$3$$$: $$$[3,5]$$$, $$$[5,7]$$$.
  • Длина $$$4$$$: $$$[2,5]$$$, $$$[3,6]$$$, $$$[4,7]$$$.
Итого: $$$5$$$.