Const
total=100;
block_sum=trunc(sqrt(total << 1));

var
num,ris,recf,bucket,output:array[-1..total] of longint;
head,tail:array[-1..block_sum] of longint;
ele:array[-1..total,-1..4] of longint;
i,n,k,x,m,l,r,ans,node_num,block_num:longint;

// bucket 存 num , recf 存 bucket

function Locate(node:longint):longint;
begin
if node mod node_num=0 then exit(node div node_num);
exit(node div node_num+1);
end;

procedure Sort(l,r,a,b:longint);
var i,j,s1,s2:longint;
begin
i:=l; j:=r; s1:=ele[(l+r) >> 1,a]; s2:=ele[(l+r) >> 1,b];
repeat
while (ele[i,a] while (ele[j,a]>s1)or((ele[j,a]=s1)and(ele[j,b]>s2)) do dec(j);
if i<=j then begin ele[0]:=ele[i]; ele[i]:=ele[j]; ele[j]:=ele[0]; inc(i); dec(j); end;
until i>=j;
if il then Sort(l,j,a,b);
end;

procedure Transfer(t:longint);
begin

end;

begin
read(n,k,m); node_num:=trunc(n/sqrt(m)); for i:=1 to n do read(num[i]);
for j:=1 to m do begin read(ele[j,1],ele[j,2]); ele[j,0]:=Locate(ele[j,1]); ele[j,3]:=i; end;
Sort(1,m,0,2); x:=0;
for i:=1 to m do if ele[i,0]<>ele[i-1,0] then begin inc(block_num); tail[block_num-1]:=i-1; head[block_num]:=i; end;
repeat
for i:=1 to n do begin bucket[i:=0; recf[i]:=0; end; // 清空
inc(x); l:=x*node_num+1; r:=ele[head[x],2]; ans:=-maxlonghint div 843;
for i:=l to r do begin dec(recf[bucket[num[i]]]); inc(bucket[num[i]]); inc(recf[bucket[num[i]]]); end; // 暴力预处理开始
for i:=1 to n do begin ris[i]:=recf[i]+ris[i-1]; if ris[i-1]-ris[i-k-1]>=0 then ans:=max(ans,i); end;
for i:=head[x] to tail[x] do // 暴力转移开始
begin
for j:=ele[i,1] to x*node_num do begin inc(bucket[num[i]]); Transfer(bucket[num[i]]); end;
for j:=ele[i,1] to x*node_num do begin dec(recf[bucket[num[i]]]); dec(bucket[num[i]]); inc(recf[bucket[num[i]]]) end; // 左边界贡献
repeat inc(r); inc(bucket[num[i]]); Transfer(bucket[num[i]]); until r=ele[i,2]; output[ele[i,3]]:=ans;
end;
until x=block_num;
for i:=1 to m do writeln(output[i]);
end.