#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct query{int x,y,poz;};query q[100005];
int v[100005],n,m,k,smax[100005];
 bool cmp(query a,query b)
 {
  return a.x/k<b.x/k;
 }
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    k=sqrt(n);
    for(int i=1;i<=m;i++)
    {
        cin>>q[i].x>>q[i].y;
        q[i].poz=i;
    }
    sort(q+1,q+m+1,cmp);
    int maxim=-99999999,summax=-99999999;
    int pozf=0;
    for(int j=q[1].x;j<=q[1].y;j++)
    {
       summax=max(summax+v[j],v[j]);
       if(summax>maxim) {maxim=summax;pozf=j;}
       smax[j]=summax;

    }
    for(int i=2;i<=m;i++)
    {

    }


}