记录编号	129518	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	东方老败	是否通过	通过
代码语言	Pascal	运行时间	0.913 s
提交时间	2014-10-20 07:09:55	内存使用	15.59 MiB

uses math;
var n,q,i,j,k,l,r:longint;
    a:array[1..50000]of longint;
	f,g:array[0..100000,0..20]of longint;
	              //f:最大值 g:最小值

procedure init;
begin
readln(n,q);
for i:=1 to n do readln(a[i]);

for i:=1 to n do
    begin f[i,0]:=a[i];g[i,0]:=a[i];end;

for j:=1 to trunc(log2(n)) do
 for i:=1 to n do
 begin
  if i+(1<<(j-1))>n then break;
  f[i,j]:=min(f[i,j-1],f[i+1<<(j-1),j-1]);
  g[i,j]:=max(g[i,j-1],g[i+1<<(j-1),j-1]);
 end;
end;

function query(x,y:longint):longint;
var i,k,maxn,minn:longint;
begin
 k:=0;
 while 1<<(k+1)<=y-x+1 do inc(k);
 maxn:=max(g[x,k],g[y-(1<<k)+1,k]);
 minn:=min(f[x,k],f[y-(1<<k)+1,k]);
 exit(maxn-minn);
end;

procedure work;
begin
for i:=1 to q do
begin
 readln(l,r);
 writeln(query(l,r));
end;
end;

begin
assign(input,'lineup.in');reset(input);
assign(output,'lineup.out');rewrite(output);
init;
work;
close(output);
end.