const
  lim=100000;
  base=666013;
var
  q:array[1..lim,1..3] of longint;
  sol:array[1..lim] of longint;
  i,j,val,n,m,k:longint;
  a:array[1..lim] of longint;
  aib,ua:array[1..lim] of longint;

procedure Sort(l, r: longint);
var
  i, j, x, y: longint;
begin
  i := l; j := r; x := q[(l+r) DIV 2,2];
  repeat
    while q[i,2] < x do i := i + 1;
    while x < q[j,2] do j := j - 1;
    if i <= j then
    begin
      y := q[i,1]; q[i,1] := q[j,1]; q[j,1] := y;
      y := q[i,2]; q[i,2] := q[j,2]; q[j,2] := y;
      y := q[i,3]; q[i,3] := q[j,3]; q[j,3] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then Sort(l, j);
  if i < r then Sort(i, r);
end;

procedure update(x,val:longint);
var
  poz:longint;
begin
  poz:=0;
  while (x<=n) do
  begin
    inc(aib[x],base+val);
    if aib[x]>=base then dec(aib[x],base);
    while (x and (1 shl poz))=0 do inc(poz);
    x:=x+(1 shl poz);
    inc(poz);
  end;
end;

function query(lo,hi:longint):longint;
var
  s1,s2,poz:longint;
begin
  s1:=0;
  poz:=0;
  while hi>0 do
  begin
    s1:=s1+aib[hi];
    if s1>=base then dec(s1,base);
    while (hi and (1 shl poz) = 0) do inc(poz);
    hi:=hi-(1 shl poz);
    inc(poz);
  end;


  dec(lo);
  s2:=0;
  poz:=0;
  while lo>0 do
  begin
    inc(s2,aib[lo]);
    if s2>=base then dec(s2,base);
    while (lo and (1 shl poz) = 0 ) do inc(poz);
    lo:=lo-(1 shl poz);
    inc(poz);
  end;

  poz:=base+s1-s2;
  if poz>=base then dec(poz,base);
  query:=poz;
end;

begin
  assign(input,'distincte.in');
  reset(input);
  readln(n,k,m);
  for i:=1 to n do
    readln(a[i]);
  for i:=1 to m do
  begin
    read(q[i,1],q[i,2]);
    q[i,3]:=i;
  end;
  sort(1,m);
  close(input);
  j:=1;
  for i:=1 to n do
  begin
    val:=a[i];
    if ua[val]>0 then update(ua[val],-val);
    update(i,val);

    while q[j,2]=i do
    begin
      sol[q[j,3]]:=query(q[j,1],q[j,2]);
      inc(j);
    end;

    ua[val]:=i;
  end;
  assign(output,'distincte.out');
  rewrite(output);
  for i:=1 to m do
    writeln(sol[i]);
  close(output);
end.