#include<fstream> 
using namespace std; 
#define lg 100003 
 
long n, m, i, x, init[lg], poz, p1, p2, l2, rsp; 
 
struct arbore_int{ 
    int x, y, sm, rp; 
}; 
arbore_int q[4*lg]; 
 
inline long max(long a, long b){ 
    return a > b ? a : b; 
} 
 
void construiesc(int st, int dr, int poz){ 
    if (st == dr){ 
        init[st] = poz; 
        return ; 
    } 
 
    int x = (st+dr) / 2; 
 
    construiesc(st, x, 2*poz); 
    construiesc(x+1, dr, 2*poz+1); 
} 
void actualizez(long poz){ 
    for (; poz; poz /= 2)
	
	{ 
        q[poz].sm = q[2*poz].sm + q[2*poz+1].sm; 
        q[poz].x = max(q[2*poz].x, q[2*poz].sm + q[2*poz+1].x); 
        q[poz].y = max(q[2*poz+1].y, q[2*poz+1].sm + q[2*poz].y); 
        q[poz].rp = max(q[2*poz].rp, q[2*poz+1].rp);
        q[poz].rp = max(q[poz].rp, q[2*poz].y + q[2*poz+1].x); 
    } 
} 
void interogare(long st, long dr, long poz){ 
    if (st >= p1 && dr <= p2){ 
 
        rsp = max(rsp, q[poz].rp); rsp = max(rsp, l2 + q[poz].x); 
        l2 = max(q[poz].y, l2 + q[poz].sm); 
 
        return ; 
    } 
    if (st > p2 || dr < p1 || st == dr) 
        return ; 
 
    int x = (st+dr) / 2; 
    interogare(st, x, 2*poz); 
    interogare(x+1, dr, 2*poz+1); 
} 
 
int main() 
{ 
   ifstream f("sequencequery.in"); 
    ofstream g("sequencequery.out"); 
 
    f>>n>>m; 
    construiesc(1, n, 1); 
 
    for (i = 1; i <= n; i ++){ 
        f>>x;
 
        poz = init[i]; 
        q[poz].x = q[poz].y = q[poz].rp = q[poz].sm = x; 
 
        actualizez(poz / 2); 
    } 
 
    for (i = 1; i <= m; i ++){ 
       f>>p1>>p2;
 
        rsp = -0x3f3f3f3f, l2 = -0x3f3f3f3f; 
        interogare(1, n, 1); 
 
        g<<rsp<<"\n"; 
    } 
      f.close();
      g.close();
     
    return 0; 
}