#11 859ms TLE

code:

#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
const int N = 100010;
int ans[N<<2],lazy[N<<2];
int a[N],n;
void push_up(int id,int l,int r){
    ans[id] = max(ans[ls(id)],ans[rs(id)]);
}
void tag_down(int id,int l,int r,int x){
    lazy[id]+=x;
    ans[id]+=x;
}
void push_down(int id,int l,int r){
    int mid = (l+r)>>1;
    tag_down(ls(id),l,mid,lazy[id]);
    tag_down(rs(id),mid+1,r,lazy[id]);
    lazy[id] = 0;
}
void build(int id,int l,int r){
    if(l==r){
        ans[id] = a[l];
        return;
    }
    int mid = (l+r)>>1;
    build(ls(id),l,mid);
    build(rs(id),mid+1,r);
    push_up(id,l,r);
}
void update(int id,int l,int r,int ql,int qr,int x){
	//printf("[%d](%d---%d)\n",id,l,r);
    if(ql<=l&&r<=qr){
        lazy[id]+=x;
        ans[id]+=x;
        return;
    }
    push_down(id,l,r);
    int mid = (l+r)>>1;
    if(ql<=mid) update(ls(id),l,mid,ql,qr,x);
    if(qr>mid) update(rs(id),mid+1,r,ql,qr,x);
    push_up(id,l,r);
}
int query(int id,int l,int r,int ql,int qr){
	//printf("[%d=%d=](%d---%d)[%d---%d]\n",id,ans[id],l,r,ql,qr);
    if(ql<=l&&r<=qr) return ans[id];
    int mid = (l+r)>>1;
    push_down(id,l,r);
    if((ql<=mid)&&(qr>mid)) return max(query(ls(id),l,mid,ql,qr),query(rs(id),mid+1,r,ql,qr));
    if(ql<=mid) return query(ls(id),l,mid,ql,qr);
    return query(rs(id),mid+1,r,ql,qr);
}
int q;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int main(){
    n = read(),q = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    build(1,1,n);
    while(q--){
        int lef,rig;
        lef = read(),rig = read();
        printf("%d\n",query(1,1,n,lef,rig));
    }
    return 0;
}