program cuburi2;
var f, g:text;
    st, dr, mij, n, m, a, b, poz:int64;
    i, iii:longint;
    s, dst, ddr:array[0..250000] of int64;
    v:array[0..250000] of longint;

procedure citire;
  begin
    readln(f,n,m);
    for i:=1 to n do
      begin
        read(f,v[i]);
        s[i]:=s[i-1]+v[i];
        dst[i]:=dst[i-1]+v[i]*(i-1);
      end;
    for i:=1 to n do
      ddr[i]:=ddr[i-1]+v[i]*(n-i);
  end;

procedure cautare;
  begin
    while st<=dr do
      begin
        mij:=(st+dr) div 2;
        if s[mij]-s[a-1]<s[b]-s[mij] then
          st:=mij+1
         else
           dr:=mij-1;
      end;
    poz:=st;
    write(g,poz,' ');
  end;

procedure calculare;
var np, cate, st, dr:int64;
  begin
    np:=n-poz;
    cate:=s[poz-1]-s[a-1];
    st:=ddr[poz-1]-ddr[a-1]-np*cate;
    np:=poz-1;
    cate:=s[b]-s[poz];
    dr:=dst[b]-dst[poz]-np*cate;
    writeln(g,st+dr);
  end;

  begin
    assign(f,'cuburi2.in'); reset(f);
    assign(g,'cuburi2.out'); rewrite(g);
    citire;
    for iii:=1 to m do
      begin
        read(f,a,b);
        st:=a;
        dr:=b;
        cautare;
        calculare;
      end;
    close(f);
    close(g);
  end.