记录编号	209883	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	Pascal	运行时间	0.936 s
提交时间	2015-11-24 13:57:06	内存使用	8.37 MiB

program zht;
var
i,j,n,m,q,w,l,r,x:longint;
a:array[0..50000] of longint;
f1,f2:array[0..50000,0..20] of longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;

function min(a,b:longint):longint;
begin
if a<b then min:=a else min:=b;
end;

begin
assign(input,'lineup.in');
assign(output,'lineup.out');
reset(input);
rewrite(output);

readln(n,m);

fillchar(f1,sizeof(f1),0);

for i:=1 to n do
begin
read(a[i]);
f1[i,0]:=a[i];
f2[i,0]:=a[i];
end;


for j:=1 to trunc(ln(n)/ln(2)) do
 for i:=1 to n+1-(1 shl j) do
  begin
  f1[i,j]:=min(f1[i,j-1],f1[i+1 shl (j-1),j-1]);
  f2[i,j]:=max(f2[i,j-1],f2[i+1 shl (j-1),j-1]);
   end;
for i:=1 to m do
 begin
 readln(l,r);
 x:=trunc(ln(r-l+1)/ln(2));
 q:=min(f1[l,x],f1[r+1-(1 shl x),x]);
 w:=max(f2[l,x],f2[r+1-(1 shl x),x]);
 writeln(w-q);
 end;

close(input);
close(output);
end.