using namespace std;

#include <iostream>
#include <fstream>

const int MAX_N = 100100;
int n, m;
int a[MAX_N];

struct segment_tree
{
    int left, right, middle, total;
    segment_tree()
    {
        left = right = middle = total = 0;
    }
} zero, neg;
segment_tree setr[MAX_N << 3];

ifstream fin("sequencequery.in");

void read()
{
    fin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        fin >> a[i];
    }
    
    neg.left = neg.right = neg.middle = neg.total = -0x3f3f3f3f;
}

void update(int node, int left, int right, int value, int position)
{
    if (left == right)
    {
        setr[node].left = setr[node].right = setr[node].middle = setr[node].total = value;
        return ;
    }
    
    int middle = (left + right) >> 1;
    int ls = node << 1, rs = ls + 1;
    
    if (position <= middle)
    {
        update(ls, left, middle, value, position);
    }
    else
    {
        update(rs, middle + 1, right, value, position);
    }
    
    setr[node].middle = max( max(setr[ls].middle, setr[rs].middle), setr[ls].right + setr[rs].left );
    setr[node].total = setr[ls].total + setr[rs].total;
    setr[node].left = max(setr[ls].left, setr[ls].total + setr[rs].left);
    setr[node].right = max(setr[rs].right, setr[ls].right + setr[rs].total);
}

void solve()
{
    for (int i = 1; i <= n; ++i)
    {
        update(1, 1, n, a[i], i);
    }
}

segment_tree solution;

void query(int node, int left, int right, int lb, int rb)
{
    if (lb <= left && right <= rb)
    {
        solution.middle = max( max(solution.middle, setr[node].middle), max(solution.right, 0) + setr[node].left );
        solution.total = solution.total + setr[node].total;
        solution.left = max(solution.left, solution.total + setr[node].left);
        solution.right = max(setr[node].right, solution.right + setr[node].total);
        
        return ;
    }
    
    int middle = (left + right) >> 1;
    int ls = node << 1, rs = ls + 1;
    
    if (lb <= middle)
    {
        query(ls, left, middle, lb, rb);
    }
    if (middle + 1 <= rb)
    {
        query(rs, middle + 1, right, lb, rb);
    }
}

void write()
{
    ofstream fout("sequencequery.out");
    
    for (int i = 1; i <= m; ++i)
    {
        int x = 0, y = 0;
        fin >> x >> y;
        
        //cout << x << ' ' << y << '\n';
        
        solution = neg;
        query(1, 1, n, x, y);
        
        fout << solution.middle << '\n';
    }
    
    fout.close();
}


int main()
{
    read(); solve(); write();
}