#include <stdio.h>
#include <algorithm>
#define modul 666013

using namespace std;

pair<int, int> v[100001];
int a[100001], arb[400001], st[400001], dr[400001], p2 = 1, n, k, m, pos[100001], used[100001], sol[100001];

bool cmp(int one, int two)
{
     return v[one].second < v[two].second;
}

void add(int val, int poz);
int query(int nod, int x, int y);

int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);

    int i, j;
    
    scanf("%d%d%d", &n, &k, &m);
    while(p2 < n)
             p2 <<= 1;
    
    for(i = 1; i <= n; ++i)
    {
          scanf("%d", &a[i]);
          st[p2 + i - 1] = dr[p2 + i - 1] = p2 + i - 1;
    }
    for(i = n + 1; i <= p2; ++i)
    {
          st[p2 + i - 1] = dr[p2 + i - 1] = p2 + i - 1;
    }
    
    for(i = p2 - 1; i > 0; --i)
    {
          st[i] = st[2 * i];
          dr[i] = dr[2 * i + 1];
    } 
    

    
    for(i = 1; i <= m; ++i)
    {
          scanf("%d%d", &v[i].first, &v[i].second);
          pos[i] = i;
    }
    
    sort(pos + 1, pos + m + 1, cmp);    
  
    for(i = 1, j = 1; i <= m; ++i)
    {
          
          for(; j <= v[pos[i]].second; ++j)
          {
                if(used[a[j]])
                {
                              add(-a[j], used[a[j]]);
                }
                add(a[j], p2 + j - 1);
          }
          
          sol[pos[i]] = query(1, p2 + v[pos[i]].first - 1, v[pos[i]].second + p2 - 1);
          //printf("%d %d\n", p2 + v[pos[i]].first - 1, p2 + v[pos[i]].second - 1);
    }
    
    for(i = 1; i <= m; ++i)
    {
          printf("%d\n", sol[i]);
    }
    
    return 0;
}


void add(int val, int poz)
{
     used[val] = poz;
     while(poz)
     {
              arb[poz] += val;
              if(arb[poz] >= modul)
                          arb[poz] -= modul;
              if(arb[poz] < 0)
                         arb[poz] += modul;
              poz >>= 1; 
     }
}

int query(int nod, int x, int y)
{
    int r = (st[nod] + dr[nod]) / 2;
    if(x == st[nod] && y == dr[nod])
         return arb[nod];
    if(y <= r)
    {
         return query(nod * 2, x, y);
    }
    if(x > r)
    {
         return query(nod * 2 + 1, x, y);
    }
    return query(nod * 2, x, r) + query(nod * 2 + 1, r + 1, y);
}