#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mx(a,b) a>b?a:b
#define mn(a,b) a<b?a:b
#define il inline
int belong, n, m;
int ans, cnt[1000010];
int answer[1000010];
int a[1000010];
struct N
{
int l, r;
int id;
}q[1000010];
il bool cmp(N a, N b)
{
return (a.l / belong) ^ (b.l / belong) ? a.l < b.l : ( ( (a.l / belong) & 1) ? a.r < b.r : a.r > b.r);
}
il int read()
{
int s = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch))
{
s = (s << 1) + (s << 3) + (ch ^ 48);
ch = getchar();
}
return s * f;
}
il void write(int x)
{
if (x<0)
{
putchar('-');
x=-x;
}
if (x>9)
write(x/10);
putchar(x%10+48);
return;
}
int main()
{
n = read();
for(int i = 1; i <= n; ++i)
a[i] = read();
m = read();
belong = 1700;
for(int i = 1; i <= m; ++i)
{
q[i].l = read();
q[i].r = read();
q[i].id = i;
}
std::sort(q + 1, q + m + 1, cmp);
int l = 0, r = 0;
for(int i = 1; i <= m; ++i)
{
int ql = q[i].l, qr = q[i].r;
while(l < ql) ans -= !--cnt[a[l++]];
while(l > ql) ans += !cnt[a[--l]]++;
while(r < qr) ans += !cnt[a[++r]]++;
while(r > qr) ans -= !--cnt[a[r--]];
answer[q[i].id] = ans;
}
for(int i = 1; i <= m; ++i)
write(answer[i]), printf("\n");
return 0;
}
顺便求卡常