#include <stdio.h>
#include <stdlib.h>

int *pl, *pr, *cl, *cr;

int najdi_minimum(int levy, int pravy, int a, int b)
{
  if (pravy - levy < 2)
    return ((namaha(levy, a, b) < namaha(pravy, a, b))?levy:pravy);
  else
  {
    int x1 = (pravy + levy + 1)/2; // Přičtení jedničky vynutí zaokrouhlení nahoru
    int x2 = x1 + 1;

    if (namaha(x1, a, b) < namaha(x2, a, b))
      return najdi_minimum(levy, x1, a, b);
    else
      return najdi_minimum(x2, pravy, a, b);
  }
}

int namaha(int i, int a, int b)
{
  return cl[i] - cl[a] - pl[a]*(i-a) + cr[i] - cr[b] - pr[b]*(b-i);
}

int main(int argc, char **argv)
{
  int n, d; int a, b;
  int i;
  int *t;
  scanf("%d %d", &n, &d);

  // Alokujeme pole větší velikosti pro snazší dynamiku
  pl = (int *) malloc((n+2)*sizeof(int));
  pr = (int *) malloc((n+2)*sizeof(int));
  cl = (int *) malloc((n+2)*sizeof(int));
  cr = (int *) malloc((n+2)*sizeof(int));
  t = (int *) malloc((n+2)*sizeof(int));

  t[0] = 0; t[n+1] = 0;
  for (i=1; i<=n; i++)
  {
    scanf("%d", &t[i]);
  }

  pl[0] = 0; cl[0] = 0;
  for (i=1; i<=n; i++)
  {
    pl[i] = pl[i-1] + t[i-1];
    cl[i] = cl[i-1] + pl[i];
  }

  pr[0] = 0; cr[0] = 0;
  for (i=n; i>0; i--)
  {
    pr[i] = pr[i+1] + t[i+1];
    cr[i] = cr[i+1] + pr[i];
  }

  for (i=0; i<d; i++)
  {
    scanf("%d %d", &a, &b);
    printf("%d\n", najdi_minimum(a, b, a, b));
  }

  free(pl); free(pr); free(cl); free(cr); free(t);

  return 0;
}