H. Сколько различных на отрезке

Дан массив из $n$ чисел. Ответьте на $q$ запросов: сколько различных значений встречается на отрезке $[l, r]$.

В первой строке — числа $n$ и $q$ ($1 \le n, q \le 2 \cdot 10^5$). Во второй — $n$ чисел ($|a_i| \le 10^9$). В следующих $q$ строках — пары $l$, $r$.

На каждый запрос выведите количество различных значений на отрезке.