#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int N, M, K;
int A[100000];
int L, R;

int b_num, b_len;
int memo[1001][1001];
int arr[100000];

vector<int> ind[100000];

int main(){
  int i, j, tmp;
  int s, t;
  int res;

  scanf("%d%d%d",&N,&M,&K);
  rep(i,N) scanf("%d",A+i);
  rep(i,N) A[i]--;

  b_len = 100;
  b_num = (N + b_len - 1) / b_len;

  for(i=0;i<N;i+=b_len){
    rep(j,M) arr[j] = -1;
    tmp = 0;
    REP(j,i,N){
      if(j%b_len==0) memo[i/b_len][j/b_len] = tmp;
      if(arr[A[j]]==-1) arr[A[j]] = j;
      else              tmp = max(tmp, j - arr[A[j]]);
    }
    memo[i/b_len][b_num] = tmp;
  }

  rep(i,N) ind[A[i]].push_back(i);

  while(K--){
    scanf("%d%d",&L,&R);
    L--;
    s = (L+b_len-1)/b_len*b_len;
    t = R/b_len*b_len;
    res = memo[s/b_len][t/b_len];

    REP(i,L,s){
      j = lower_bound(ind[A[i]].begin(), ind[A[i]].end(), R) - ind[A[i]].begin() - 1;
      if(j<0) continue;
      res = max(res, ind[A[i]][j] - i);
    }

    for(i=R-1;i>=t;i--){
      j = lower_bound(ind[A[i]].begin(), ind[A[i]].end(), L) - ind[A[i]].begin();
      if(j==ind[A[i]].size()) continue;
      res = max(res, i - ind[A[i]][j]);
    }

    printf("%d\n", res);
  }

  return 0;
}