G. Ровно k раз

Для каждого запроса $(l, r, k)$ нужно сказать, сколько различных значений встречается на отрезке ровно $k$ раз.

В первой строке $n$ и $q$ ($1 \le n, q \le 10^5$). Во второй строке $n$ чисел $a_i$ ($1 \le a_i \le 10^9$).

В следующих $q$ строках по три числа $l$, $r$ и $k$ ($1 \le l \le r \le n$, $1 \le k \le n$).

Для каждого запроса выведите количество значений, встречающихся на отрезке ровно $k$ раз.