#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

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

const int MAX_N = 100100;
const int INF = 1 << 30;

class SegmentTree {
public:
  SegmentTree();
  int query_segment(int a, int b);
  void update_tree(int pos, int val);
private:
  void build_tree(int node, int lo, int hi);
  int query(int node, int lo, int hi, int a, int b);
  struct SegTreeNode {
    int minim, maxim;
    int best;
  };
  vector<SegTreeNode> tree;
  int min_prefix;
};

int N, M;
int v[MAX_N];

int main() {
  fin >> N >> M;
  for (int i = 1; i <= N; ++i) {
    fin >> v[i];
    v[i] += v[i - 1];
  }
  SegmentTree aint;

  for (int i = 1, a, b; i <= M; ++i) {
    fin >> a >> b;
    fout << aint.query_segment(a, b) << '\n';
  }

  return 0;
}

SegmentTree::SegmentTree() {
  tree.resize(8 * N);
  build_tree(1, 1, N);
}

void SegmentTree::build_tree(int node, int lo, int hi) {
  if (lo == hi) {
    tree[node].minim = v[lo - 1];
    tree[node].maxim = v[lo];
    tree[node].best = v[lo] - v[lo - 1];
  } else {
    int mid = lo + (hi - lo) / 2;
    int son1 = node * 2;
    int son2 = son1 + 1;
    build_tree(son1, lo, mid);
    build_tree(son2, mid + 1, hi);
    
    tree[node].minim = min(tree[son1].minim, tree[son2].minim);
    tree[node].maxim = max(tree[son1].maxim, tree[son2].maxim);
    tree[node].best = max(tree[son1].best,
                          max(tree[son2].best, 
                              tree[son2].maxim - tree[son1].minim));
  }
}

inline int SegmentTree::query_segment(int a, int b) {
  min_prefix = INF;
  return query(1, 1, N, a, b);
}

int SegmentTree::query(int node, int lo, int hi, int a, int b) {
  if (a <= lo && b >= hi) {
    int result = tree[node].best;
    if (min_prefix != INF) {
      result = max(result, tree[node].maxim - min_prefix);
    }
    min_prefix = min(min_prefix, tree[node].minim);
    return result;
  }
  
  int result = -INF;
  int son1 = node * 2;
  int son2 = son1 + 1;
  int mid = lo + (hi - lo) / 2;
  if (a <= mid) {
    result = max(result, query(son1, lo, mid, a, b));
  }
  if (b > mid) {
    result = max(result, query(son2, mid + 1, hi, a, b));
  }
  return result;
}