For each \(x = 1,\ldots,N\), let \(\mathrm{idx}_x\) be the array of indices \(i\) such that \(A_i = x\), in the increasing order.

Then, each query can be interpreted as follows.

Given \(L, R\), and \(X\), find how many elements of \(\mathrm{idx}_X\) are between \(L\) and \(R\), inclusive.

This problem can be solved by finding the position in \(\mathrm{idx}_X\) of the smallest element that is greater than or equal to \(L\), and the smallest element that is strictly greater than \(R\), both of which can be found with binary search in a total of \(\mathrm{Ο}(\log N)\) time.

The total time complexity is \(\mathrm{Ο}(N+Q\log N)\).

Sample code (C++):

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;

	vector<vector<int>> idx(n + 1);
	for(int i = 0; i < n; i++) {
		int a;
		cin >> a;
		idx[a].push_back(i);
	}

	int q;
	cin >> q;

	while(q--) {
		int l, r, x;
		cin >> l >> r >> x;
		cout << lower_bound(idx[x].begin(), idx[x].end(), r) - lower_bound(idx[x].begin(), idx[x].end(), l - 1) << endl;
	}
}