#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cmath>

char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

using namespace std;

const int N = 1000000 + 10, M = N;

int n, m, res = 0;
int a[N], pos[N], cnt[N];
int ans[M];

struct Q
{
    int l, r, k;
    
    bool operator <(const Q &t)const
    {
        return pos[l] == pos[t.l] ? r < t.r : pos[l] < pos[t.l];
    }
}q[M];

inline void Add(register int x)
{
    if (!cnt[a[x]])
        res ++ ;
    cnt[a[x]] ++ ;
}

inline void Sub(register int x)
{
    if (cnt[a[x]] == 1)
        res -- ;
    cnt[a[x]] -- ;
}

template<typename T> inline void read(register T &qwq)
{
    register T x = 0, f = 1;
    register char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = nc();
    qwq = x * f;
    return;
}

template<typename T> inline void write(register T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}

int main()
{
    read(n);
    
    register int siz = sqrt(n);
    for (register int i = 1; i <= n; i ++ )
        read(a[i]), pos[i] = i / siz;
        
    read(m);
    
    for (register int i = 1; i <= m; i ++ )
        read(q[i].l), read(q[i].r), q[i].k = i;
        
    sort(q + 1, q + 1 + m);
    
    register int l = 1, r = 0;
    for (register 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) Sub(l ++ );
        while (r > q[i].r) Sub(r -- );
        
        ans[q[i].k] = res;
    }
    
    for (register int i = 1; i <= m; i ++ )
        write(ans[i]), putchar('\n');
        
    return 0;
}

评测记录