Program Segment_Tree;
Type
  St_Tree = ^Tree;
  Tree = Record
    Max, Min:  LongInt;
    Left, Right: St_Tree;
    LeftN, RightN: LongInt;
  End;
Var
  a: Array[0..200005]Of LongInt;
  Root: St_Tree;
  N, Q: LongInt;
  MaxN, MinN: LongInt;
Function FMin(x, y: LongInt): LongInt;
Begin If x < y Then FMin := x Else FMin := y; End;
Function FMax(x, y: LongInt): LongInt;
Begin If x > y Then FMax := x Else FMax := y; End;
Procedure Build_Tree(Now: St_Tree; L, r: LongInt);Var k: LongInt;
Begin
  Now^.LeftN := L; Now^.RightN := r;
  If (r - L) > 1 Then
  Begin
    k := (r + L)Div 2;
    New(Now^.Left); Build_Tree(Now^.Left, L, k);
    New(Now^.Right); Build_Tree(Now^.Right, k, r);
    Now^.Max := FMax(Now^.Left^.Max, Now^.Right^.Max);
    Now^.Min := FMin(Now^.Left^.Min, Now^.Right^.Min);
  End Else
  Begin
    Now^.Max := FMax(a[L], a[r]);
    Now^.Min := FMin(a[L], a[r]);
  End;
End;
Procedure Find(Now: St_Tree; L, r: LongInt);Var LN, rN, k: LongInt;
Begin
  LN := Now^.LeftN; rN := Now^.RightN; k := (LN + rN) Div 2;
  If (L = LN)And(r = rN) Then
  Begin
    MaxN := FMax(MaxN, Now^.Max);
    MinN := FMin(MinN, Now^.Min); Exit;
  End;
  If L >= k Then Find(Now^.Right, L, r)
    Else If r <= k Then Find(Now^.Left, L, r)
      Else Begin Find(Now^.Left, L, k); Find(Now^.Right, k, r); End;
End;
Procedure Init;Var i: LongInt;
Begin
  FillChar(a, SizeOf(a), 0);
  ReadLn(N, Q);
  For i := 1 To N Do ReadLn(a[i]);
End;
Procedure Main;
Begin
  New(Root); Build_Tree(Root, 1, N);
End;
Procedure Print;Var i, L, r: LongInt;
Begin
  For i := 1 To Q Do
  Begin
    ReadLn(L, r); MaxN := 0; MinN := MaxInt;
    If L < r Then
    Begin
      Find(Root, L, r);
      WriteLn(MaxN - MinN);
    End Else WriteLn(0);
  End;
End;
Begin
  Init;
  Main;
  Print;
End.