#include<bits/stdc++.h>

 using namespace std;

 const int N =;

 const int S =;

 int a[N],res[S][N],occ[N];

 int ans[N];

 //一种很神奇的分块写法

 //想办法 在其他题目扩展

 struct query

 {

     int L,R,id;

     bool operator <(const query& a)const

     {

         return R<a.R;

     }

 }q[N];

 int main()

 {

     int n,m,k;

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

     int s=sqrt(n);

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

     for (int i=;i*s<n;i++)//预处理0-->sqrt(n)个块，每块的宽度这里并不一定相同

     {                       //这里是从i*s-->n 都计算出区间的最大值

         for (int j=;j<=m;j++) occ[j]=-;

         int now=;

         for (int j=i*s;j<n;j++)

         {

             if (occ[a[j]]==-) occ[a[j]]=j;

             else now=max(now,j-occ[a[j]]);

             res[i][j]=now;

         }

     }

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

     scanf("%d%d",&q[i].L,&q[i].R),q[i].id=i,q[i].L--,q[i].R--;

     sort(q,q+k);//按询问R排序

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

         occ[i]=-;

     int r=;

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

     {

         while (r<q[i].R)//q[i].L<q[i].R;

         {

             ++r;

             occ[a[r]]=r;//预处理出前几个

         }

         int tmp=res[q[i].L/s+][q[i].R];//计算已经可以分块的数据

         for (int j=q[i].L;j<(q[i].L/s+)*s&&j<=q[i].R;j++)

         tmp=max(tmp,occ[a[j]]-j);//利用询问的单调询问开始不足一块的数据

         ans[q[i].id]=tmp;

     }

     for (int i=;i<k;i++) printf("%d\n",ans[i]);

     return ;

 }