RT，优化后莫队只能卡到44pts，再求优化

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <queue>
//#include <map>

#define endl "\n"
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define int long long
#define LL long long
#define ULL unsigned long long
#define INF LLONG_MAX / 3 
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define mid(a, b) (a + b) >> 1 
#define PII pair <int, int>
#define inl inline
#define re register

const int N = 2e6 + 7, M = 2e3 + 7, P = 131, MOD = 1e9 + 7;

using namespace std;

inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if(c == '-') flag = true;
    else num = c - '0';
    while(isdigit(c = getchar())) num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
} 

int t;

int n, m, len, ans;

int val[N]; 

int pos[N], cnt[N];

//query

struct query

{
	int L, R, k;
}q[N];

int put_[N];

//不带修基础莫队 

inl void init()

{
	n = read();
	int len = sqrt(n);
	for (re int i = 1; i <= n; i ++ ) val[i] = read(), pos[i] = (i - 1) / len + 1;
}

bool cmp(query x, query y)

{
	//核心
	if (pos[x.L] != pos[y.L]) return pos[x.L] < pos[y.L];
	if (pos[x.L] & 1) return x.R > y.R; 
	return x.R < y.R; 
}

inl void add(int v)

{
	cnt[val[v]] ++;
	if (cnt[val[v]] == 1) ans ++;
}

inl void del(int v)

{
	cnt[val[v]] --;
	if (cnt[val[v]] == 0) ans --;
}

inl void solve()

{
    init();

	m = read();
	for (re int i = 1; i <= m; i ++ ) q[i].L = read(), q[i].R = read(), q[i].k = i;
	sort(q + 1, q + m + 1, cmp);
	int L = 1, R = 0;
	for (re int i = 1; i <= m; i ++ )
	{
		while (L < q[i].L) del(L ++);
		while (R > q[i].R) del(R --);
		while (L > q[i].L) add(-- L);
		while (R < q[i].R) add(++ R);
		put_[q[i].k] = ans;
	}
	
	for (re int i = 1; i <= m; i ++ ) cout << put_[i] << endl;
    //puts("");
}

signed main()

{
    IOS;

    t = 1;
    //t = read();
    while (t -- ) solve();
}