思路跟 P4396 差不多，但是 WA 了

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

namespace fastIO
{
	template<typename T> inline void read(T &t)
	{
		T x = 0;
		int f = 0;
		char ch = getchar();
		while (!isdigit(ch)) f ^= !(ch ^ 45), ch = getchar();
		while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
		t = f ? -x : x;
	}
	template<typename T, typename ...Args> inline void read(T &x, Args&... args)
	{
		read(x), read(args...);
	}
}
using namespace fastIO;

const int N = 1000005;
int n, m, block, num;
int a[N], b[N << 1];
int cnt[N << 1], sum[N << 1];
int ans[N], res;
int st[N << 1], ed[N << 1], pos[N << 1];
struct Query
{
	int l, r, k, id;
	bool operator<(const Query &x) const {return pos[l] ^ pos[x.l] ? l < x.l : pos[l] & 1 ? r < x.r : r > x.r;}
}q[N];

void add(int x)
{
	cnt[a[x]] ++ ;
	sum[pos[a[x]]] ++ ;
}
void del(int x)
{
	cnt[a[x]] -- ;
	sum[pos[a[x]]] -- ;
}
int calc(int l, int r)
{
	int res = 0;
	if (pos[l] == pos[r])
	{
		for (int i = l; i <= r; i ++ ) res += cnt[i];
		return res;
	}
	for (int i = l; i <= ed[pos[l]]; i ++ ) res += cnt[i];
	for (int i = pos[l] + 1; i < pos[r]; i ++ ) res += sum[i];
	for (int i = st[pos[r]]; i <= r; i ++ ) res += cnt[i];
	return res;
}

int main()
{
	read(n);
	for (int i = 1; i <= n; i ++ ) read(a[i]), b[i] = a[i];
	read(m);
	for (int i = 1; i <= m; i ++ ) read(q[i].l, q[i].r, q[i].k), q[i].id = i, b[i + n] = q[i].k;

	sort(b + 1, b + n + m + 1);
	int len = unique(b + 1, b + n + m + 1) - b - 1;
	for (int i = 1; i <= n; i ++ ) a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
	for (int i = 1; i <= m; i ++ ) q[i].k = lower_bound(b + 1, b + len + 1, q[i].k) - b;

	block = sqrt(len), num = (len - 1) / block + 1;
	for (int i = 1; i <= len; i ++ ) pos[i] = (i - 1) / block + 1;
	for (int i = 1; i <= num; i ++ ) st[i] = (i - 1) * block + 1, ed[i] = min(i * block, len);

	sort(q + 1, q + m + 1);

	int l = 1, r = 0;
	for (int i = 1; i <= m; i ++ )
	{
		while (l > q[i].l) add( -- l);
		while (r < q[i].r) add( ++ r);
		while (l < q[i].l) del(l ++ );
		while (r > q[i].r) del(r -- );
		ans[q[i].id] = calc(q[i].k + 1, len);
	}
	for (int i = 1; i <= m; i ++ ) printf("%d\n", ans[i]);
	return 0;
}