for j:=1 to ln(n)/ln(2)
for i:=1 to n-(1 shl j)+1 do
f[i,j]:=min(f[i,j-1],f[i+(1 shl (j-1),j-1];
f[l,r]:=min(f[l,j],f[r-(1 shl j)+1,j]; j=ln(r-l+1)/ln(2);
ln(n)/ln(2)=log(2,n);
Program lineup; const maxn=50000; maxq=200000; maxh=1000000; var n,q,i,j,l,r,k:longint; a:array[1..maxh] of longint; f,h:array[1..maxh,0..16] of longint;//f mintall h hightall function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; begin read(n,q); for i:=1 to n do begin read(a[i]); f[i,0]:=a[i]; h[i,0]:=a[i]; end; for j:=1 to trunc(ln(n)/ln(2)) do //f[i,j]:=min(f[i,j-1],f[i+2^(j-1),j-1] i<=n-2^j for i:=1 to n-(1 shl j)+1 do begin f[i,j]:=min(f[i,j-1],f[i+1 shl (j-1),j-1]); h[i,j]:=max(h[i,j-1],h[i+1 shl (j-1),j-1]); end; for i:=1 to q do begin read(l,r); j:=(r-l+1); j:=trunc(ln(j)/ln(2)); writeln(max(h[l,j],h[r-1 shl j +1,j])-min(f[l,j],f[r-1 shl j +1,j])); end; end.