#include <cstdio>

using namespace std;

FILE *fin;

const int MAXN = 100001;

struct Node {
  long long pref, suff, sum, ssm;
};

Node aint[4 * MAXN];

inline long long maximum(long long a, long long b) {
  if (a < b)
    return b;
  return a;
}

void init_dfs(int node, int left, int right) {
  if (left == right) {
    int num;
    fscanf(fin, "%d", &num);
    aint[node] = {num, num, num, num};
    return;
  }
  int mid = (left + right) / 2;
  init_dfs(2 * node, left, mid);
  init_dfs(2 * node + 1, mid + 1, right);
  aint[node].sum = aint[2 * node].sum + aint[2 * node + 1].sum;
  aint[node].pref = maximum(aint[2 * node].pref, aint[2 * node].sum + aint[2 * node +1].pref);
  aint[node].suff = maximum(aint[2 * node + 1].suff, aint[2 * node + 1].sum + aint[2 * node].suff);
  aint[node].ssm = maximum(aint[2 * node].ssm, aint[2 * node + 1].ssm);
  aint[node].ssm = maximum(aint[node].ssm, aint[2 * node].suff + aint[2 * node + 1].pref);
}

long long ans, curr;
int x, y;

void query(int node, int left, int right) {
  if (x <= left && right <= y) {
    curr = maximum(0LL, curr);
    ans = maximum(ans, aint[node].ssm);
    ans = maximum(ans, aint[node].pref + curr);
    curr = maximum(aint[node].suff, curr + aint[node].sum);
    return;
  }
  int mid = (left + right) / 2;
  if (x <= mid)
    query(2 * node, left, mid);
  if(mid < y)
    query(2 * node + 1, mid + 1, right);
}

const long long NEG_INF = -1e11;

int main()
{
    FILE *fout;
    int n, m, i;
    fin = fopen("sequencequery.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    init_dfs(1, 1, n);
    fout = fopen("sequencequery.out", "w");
    for (i = 0; i < m; ++i) {
      fscanf(fin, "%d%d", &x, &y);
      curr = 0LL; ans = NEG_INF;
      query(1, 1, n);
      fprintf(fout, "%lld\n", ans);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}