/*

     题意：从i开始，之前出现过的就是之前的值，否则递增，问第p个数字是多少

     莫队算法：先把a[i+p-1]等效到最前方没有它的a[j]，问题转变为求[l, r]上不重复数字有几个，裸莫队:)

 */

 #include <cstdio>

 #include <algorithm>

 #include <map>

 #include <set>

 #include <vector>

 #include <cmath>

 #include <cstring>

 using namespace std;

 const int MAXN = 2e6 + ;

 const int INF = 0x3f3f3f3f;

 map<int, int> table;

 vector<int> V[MAXN];

 int cnt[MAXN];

 int a[MAXN];

 int ans[MAXN];

 struct Data

 {

     int b, l, r, id;

     Data () {}

     Data (int b, int l, int r, int id) : b (b), l (l), r (r), id (id) {};

 }data[MAXN];

 int n, m;

 int ret;

 bool cmp(Data x, Data y)

 {

     if (x.b == y.b)    return x.r < y.r;

     else    return x.b < y.b;

 }

 void updata(int v)

 {

     if (v == )    ret++;

     else if (v == )    ret--;

 }

 void Modui(void)

 {

     sort (data+, data++m, cmp);

     memset (cnt, , sizeof (cnt));

     int l = , r = ;    ret = ;

     for (int i=; i<=m; ++i)

     {

         while (data[i].l < l)

         {

             ++cnt[a[--l]];

             if (cnt[a[l]] == )    ret++;

         }

         while (data[i].l > l)

         {

             --cnt[a[l]];

             if (cnt[a[l]] == )    ret--;

             l++;

         }

         while (data[i].r > r)

         {

             ++cnt[a[++r]];

             if (cnt[a[r]] == )    ret++;

         }

         while (data[i].r < r)

         {

             --cnt[a[r]];

             if (cnt[a[r]] == )    ret--;

             r--;

         }

         ans[data[i].id] = ret;

     }

     for (int i=; i<=m; ++i)

     {

         printf ("%d\n", ans[i]);

     }

 }

 int main(void)        //Gym - 100496D Data Mining

 {

     // freopen ("D.in", "r", stdin);

     freopen ("data.in", "r", stdin);

     freopen ("data.out", "w", stdout);

     while (scanf ("%d", &n) == )

     {

         table.clear ();

         for (int i=; i<=n; ++i)    V[i].clear ();

         int num = ;

         for (int i=; i<=n; ++i)

         {

             scanf ("%d", &a[i]);

             a[i] = table[a[i]] ? table[a[i]] : table[a[i]] = ++num;

             V[a[i]].push_back (i);

         }

         int block = (int) sqrt (n * 1.0);

         scanf ("%d", &m);

         for (int i=; i<=m; ++i)

         {

             int l, r;    scanf ("%d%d", &l, &r);

             r = l + r - ;

             int pos = lower_bound (V[a[r]].begin (), V[a[r]].end (), l) - V[a[r]].begin ();

             r = V[a[r]][pos];

             data[i] = Data (l / block, l, r, i);

         }

         Modui ();

     }

     return ;

 }