Как решить спой Dquery с еще одним ограничением

Я решил эту спой DQUERY
проблема с использованием алгоритмов МО во временной сложности N*Sqrt(N),
Но теперь я хочу еще одно ограничение на каждый запрос, то есть теперь каждый запрос содержит четыре целых числа i,j,x,yтакие как:

(1 ≤ i ≤ j ≤ n)
(1 ≤ x ≤ y ≤ 10^6)

Для каждого d-запроса (i, j) вы должны вернуть количество различных элементов в подпоследовательности ai, ai + 1, …, aj, которое больше или равно x и меньше или равно y,
Например:
Если n=5 элемент массива быть

1 1 2 1 3

тогда для запроса (i, j, x, y):

1 5 2 3

ответ будет:

2

потому что в диапазоне от i=1 в j=5 три отдельных элемента{1,2,3} присутствует, но только два элемента{2,3} присутствует в диапазоне x=2 в y=3. Так ответ 2,
Я получаю решение во времени сложности (Q * SQRT (N)ИКС), помогите пожалуйста как решить этот вопрос с эффективное время сложность меньше, чем (QSQRT (N) * Х).