#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <iomanip>

#include   <cstdlib>

#include    <cstdio>

#include    <string>

#include    <vector>

#include    <bitset>

#include    <cctype>

#include     <queue>

#include     <cmath>

#include      <list>

#include       <map>

#include       <set>

//#include <unordered_map>

//#include <unordered_set>

//#include<ext/pb_ds/assoc_container.hpp>

//#include<ext/pb_ds/hash_policy.hpp>

using namespace std;

//#pragma GCC optimize(3)

//#pragma comment(linker, "/STACK:102400000,102400000")  //c++

#define lson (l , mid , rt << 1)

#define rson (mid + 1 , r , rt << 1 | 1)

#define debug(x) cerr << #x << " = " << x << "\n";

#define pb push_back

#define pq priority_queue

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll ,ll > pll;

typedef pair<int ,int > pii;

typedef pair<int ,pii> p3;

//priority_queue<int> q;//这是一个大根堆q

//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q

//__gnu_pbds::cc_hash_table<int,int>ret[11];    //这是很快的hash_map

#define fi first

#define se second

//#define endl '\n'

#define OKC ios::sync_with_stdio(false);cin.tie(0)

#define FT(A,B,C) for(int A=B;A <= C;++A)  //用来压行

#define REP(i , j , k)  for(int i = j ; i <  k ; ++i)

//priority_queue<int ,vector<int>, greater<int> >que;

const ll mos = 0x7FFFFFFFLL;  //

const ll nmos = 0x80000000LL;  //-2147483648

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3fLL; //

const double PI=acos(-1.0);

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

/*-----------------------showtime----------------------*/

            const int maxn = 2e6+;

            int a[maxn],sum[maxn],nx[maxn],x[maxn],ans[maxn],cnt[maxn];

            int n,c,m;

            struct node

            {

                int l,r,id;

            }q[maxn];

            bool cmp(node a,node b){

                if(a.l == b.l)

                    return a.r < b.r;

                return a.l < b.l;

            }

            int lowbit(int x){

                return x & (-x);

            }

            void add(int x,int c){

                while(x <= n){

                    sum[x] += c;

                    x+=lowbit(x);

                }

            }

            int query(int x){

                int res = ;

                while(x > ){

                    res += sum[x];

                    x -= lowbit(x);

                }

                return res;

            }

int main(){

            scanf("%d%d%d", &n, &c, &m);

            for(int i=; i<=n; i++) scanf("%d", &a[i]);

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

                cnt[a[i]]++;

                if(cnt[a[i]] == )add(i,);

            }

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

                scanf("%d%d", &q[i].l, &q[i].r);

                q[i].id = i;

            }

            for(int i=n; i>=; i--){

                nx[i] = x[a[i]];

                x[a[i]] = i;

            }

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

            int le = ;

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

                while(le < q[i].l){

                    if(nx[le] > ) add(nx[le],-);

                    if(nx[nx[le]] > )add (nx[nx[le]], );

                    le++;

                }

                ans[q[i].id] = query(q[i].r) - query(q[i].l-);

            }

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

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

            }

            return ;

}