// https://www.infoarena.ro/problema/sequencequery

#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC optimize("O3,unroll-loops")
#pragma GCC target(                                                            \
    "avx512f,avx512bw,avx512dq,avx512cd,avx512vl,bmi,bmi2,lzcnt,popcnt,fma")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")

// #define _USE_MATH_DEFINES

#include <bits/stdc++.h>

using namespace std;

using int64 = int64_t;
using uint64 = uint64_t;
using int32 = int32_t;
using uint32 = uint32_t;
using int16 = int16_t;
using uint16 = uint16_t;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define all(x) (x).begin(), (x).end()
#define allg(x) (x).begin(), (x).end(), greater<int>()
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define rfor(i, st, dr) for (auto i = (st); i <= (dr); ++i)
#define for0(i, n) for (auto i = 0; i < (n); ++i)
#define rfor0(i, n) for (auto i = (n) - 1; i >= 0; --i)
#define for1(i, n) for (auto i = 1; i <= (n); ++i)
#define rfor1(i, n) for (auto i = (n); i >= 1; --i)
#define foreach(x, a) for (auto &x : a)
#define cforeach(x, a) for (const auto &x : a)
#define ft first
#define sd second
#define cendl cout << "\n"
#define fendl fout << "\n"
#define FASTIO                                                                 \
  ios::sync_with_stdio(false);                                                 \
  cin.tie(nullptr);

// #define int int64

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

// FILE* fin = fopen("", "r");
// FILE* fout = fopen("", "w");

const int NRMAX = 100000;

struct Arbore {
  int sum, pref, suff, best;
} arb[2 * NRMAX];
int v[NRMAX], rez = 0;

Arbore combina(Arbore L, Arbore R) {
  Arbore t;

  t.sum = L.sum + R.sum;
  t.best = max(L.suff + R.pref, max(L.best, R.best));
  t.pref = max(L.pref, L.sum + R.pref);
  t.suff = max(R.suff, R.sum + L.suff);

  return t;
}
void build(int x, int st, int dr) {
  if (st == dr) {
    arb[x].sum = v[st];
    arb[x].best = v[st];
    arb[x].pref = v[st];
    arb[x].suff = v[st];
    return;
  }

  int m = (st + dr) / 2;
  int ls = x + 1;
  int rs = x + 2 * (m - st + 1);

  build(ls, st, m);
  build(rs, m + 1, dr);

  arb[x] = combina(arb[ls], arb[rs]);
}

Arbore query(int x, int st, int dr, int a, int b) {
  if (a <= st && dr <= b) {
    return arb[x];
  }

  int m = (st + dr) / 2;
  int ls = x + 1;
  int rs = x + 2 * (m - st + 1);

  if (b <= m)
    return query(ls, st, m, a, b);
  if (a > m)
    return query(rs, m + 1, dr, a, b);

  Arbore L = query(ls, st, m, a, b);
  Arbore R = query(rs, m + 1, dr, a, b);

  return combina(L, R);
}

int32 main() {
  // FASTIO;

  int n, m, i, x, y;

  fin >> n >> m;
  for (i = 0; i < n; ++i) {
    fin >> v[i];
  }

  build(0, 0, n - 1);

  while (m--) {
    fin >> x >> y;

    fout << query(0, 0, n - 1, x - 1, y - 1).best << "\n";
  }

  return 0;
}