var f,g:text;
    i,j,n,k,x,y:integer;
    b:array[1..100000] of integer;
    d:array[1..22000,1..22000] of integer;

function maks(a,b:longint):longint;
begin
if a>=b then maks:=a
        else maks:=b;
end;

begin
assign(f,'knjige.in');
reset(f);
assign(g,'knjige.out');
rewrite(g);
readln(f,n,k);
for i:=1 to n do
begin
read(f,b[i]);
d[i,i]:=0;
end;
readln(f);
for i:=1 to n-1 do
for j:=1 to n-i do
d[j,i+j]:=maks(d[j,i+j-1],d[j+1,i+j])+ord(b[i+j]=b[j]);
for i:=1 to k do
begin
readln(f,x,y);
j:=y-x+1-d[x,y];
writeln(g,j);
end;
close(f);
close(g);
end.

