#define _CRT_SECURE_NO_DEPRECATE#include<stdio.h>  #include<string.h>  #include<cstring>#include<algorithm>  #include<queue>  #include<math.h>  #include<time.h>#include<vector>#include<iostream>#include<map>using namespace std;typedef long long int LL;const int MAXN = 100000 + 10;int belong[MAXN], block, num, L[MAXN], R[MAXN];int n, m, q;int a[MAXN], last[MAXN][500], first[MAXN][500], Ans[500][500];int tim[MAXN], times, Pos[MAXN];int cal(int st, int ed){    int ans = 0;    for (int i = L[st]; i <= R[st]; i++){        ans = max(ans, last[a[i]][ed] - i);    }    return ans;}void build(){    block = (int)sqrt(n + 0.5);    num = n / block; if (n%block){ num++; }    for (int i = 1; i <= num; i++){        L[i] = (i - 1)*block + 1; R[i] = i*block;    }    R[num] = n;    for (int i = 1; i <= n; i++){        belong[i] = ((i - 1) / block) + 1;    }    memset(last, 0, sizeof(last)); memset(first, 0, sizeof(first));    memset(Ans, 0, sizeof(Ans)); times = 0;    for (int i = 1; i <= n; i++){        last[a[i]][belong[i]] = i;    }    for (int i = n; i>0; i--){        first[a[i]][belong[i]] = i;    }    for (int i = 1; i <= m; i++){        for (int j = 1; j <= num; j++){            if (!last[i][j]){ last[i][j] = last[i][j - 1]; }        }        for (int j = num; j; j--){            if (!first[i][j]){ first[i][j] = first[i][j + 1]; }        }    }    for (int i = num; i; i--){        for (int j = i; j <= num; j++){            Ans[i][j] = max(max(Ans[i + 1][j], Ans[i][j - 1]), cal(i, j));        }    }}int query(int st, int ed){    int ans = 0; times++;    if (belong[st] == belong[ed]){        for (int i = st; i <= ed; i++){            if (tim[a[i]] != times){ Pos[a[i]] = i; tim[a[i]] = times; }            else{ ans = max(ans, i - Pos[a[i]]); }        }        return ans;    }    for (int i = st; i <= R[belong[st]]; i++){        if (tim[a[i]] != times){ Pos[a[i]] = i; tim[a[i]] = times; }        else{ ans = max(ans, i - Pos[a[i]]); }        ans = max(ans, last[a[i]][belong[ed] - 1] - i);    }    ans = max(ans, Ans[belong[st] + 1][belong[ed] - 1]);    for (int i = L[belong[ed]]; i <= ed; i++){        if (tim[a[i]] != times){ Pos[a[i]] = i; tim[a[i]] = times; }        else{ ans = max(ans, i - Pos[a[i]]); }        ans = max(ans, i - first[a[i]][belong[st] + 1]);    }    return ans;}int main(){    //#ifdef kirito    //    freopen("in.txt", "r", stdin);    //    freopen("out.txt", "w", stdout);    //#endif    //    int start = clock();    while (~scanf("%d%d%d", &n, &m, &q)){        for (int i = 1; i <= n; i++){ scanf("%d", &a[i]); }        build(); int st, ed;        for (int i = 1; i <= q; i++){            scanf("%d%d", &st, &ed);            printf("%d\n", query(st, ed));        }    }    //#ifdef LOCAL_TIME    //    cout << "[Finished in " << clock() - start << " ms]" << endl;    //#endif    return 0;}