#include<fstream.h>    
     
#define lg 100003    
     
 int n, m, i, x, init[lg], poz, p1, p2, l2, rsp;    
     
 struct arbore_int{    
     int x, y, sm, rp;    
 };    
 arbore_int q[3*lg];    
     
 inline int max(int a, int 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(int 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(int st, int dr, int 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");    
     fstream 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 = -1000000, l2 = -1000000;    
         interogare(1, n, 1);    
     
         g<<rsp<<"\n";    
     }    
       f.close();  
       g.close();  
     return 0;    
 }