With an array of size  ≤ 10⁵, and with every a[i] in the range 1 ≤ a[i] ≤ 10⁵, there are  ≤ 10⁵ queries.

Each query is of the form [l, r, k], and the output should the number of elements that appear  ≥ k times in a[l]..a[j]. I've though on this for a while, and can't get any idea how to solve this. I've seen a similar problem before but can't find the statement anywhere.

I'm thinking squareroot decomposition could work, but have no clue to proceed. Thanks for any help!