#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int N, M, List[100001], i;
struct Pair{
    int val, cant;
};
struct Node{
    Pair present;
    Pair left;
    Pair right;
    int sum;
};
Node Best(Node A, Node B, int a, int b, int mid);
class BTree{
    Node V[400001];
    void Change(int target, int val, int a, int b, int position){
        int mid=(a+b)/2;
        if(a==b){
            V[position].left.val=V[position].right.val=V[position].present.val=V[position].sum=val;
            V[position].left.cant=V[position].right.cant=V[position].present.cant=1;
            return;
        }
        if(target<=mid) Change(target, val, a, mid, 2*position);
        else Change(target, val, mid+1, b, 2*position+1);
        V[position]=Best(V[2*position], V[2*position+1], a, b, mid);
        return;
    }
    Node Query(int left, int right, int a, int b, int position){
        int mid=(a+b)/2;
        if(a==left && b==right) return V[position];
        else if(right<=mid) return Query(left, right, a, mid, 2*position);
        else if(left>mid) return Query(left, right, mid+1, b, 2*position+1);
        else return Best(Query(left, mid, a, mid, 2*position), Query(mid+1, right, mid+1, b, 2*position+1), a, b, mid);
    }
public:
    void Set(int target, int val){
        Change(target, val, 1, N, 1);
        return;
    }
    void Get(int left, int right){
        fout<<Query(left, right, 1, N, 1).present.val<<"\n";
        return;
    }
};
BTree Arb;
int main()
{
    fin>>N>>M;
    for(i=1; i<=N; ++i){
        fin>>List[i];
        Arb.Set(i, List[i]);
    }
    for(i=1; i<=M; ++i){
        int left, right;
        fin>>left>>right;
        Arb.Get(left, right);
    }
    return 0;
}
Node Best(Node A, Node B, int a, int b, int mid){
    Node C;
    C.sum=A.sum+B.sum;
    if(A.right.val+B.left.val>=A.present.val && A.right.val+B.left.val>=B.present.val) {C.present.val=A.right.val+B.left.val; C.present.cant=A.right.cant+B.left.cant;}
    else if(A.present.val>=B.present.val) C.present=A.present;
    else C.present=B.present;
    C.left=A.left;
    if(A.left.cant==mid-a+1 && B.left.val>0) {C.left.cant+=B.left.cant; C.left.val+=B.left.val;}
    if(A.sum+B.left.val>C.left.val) {C.left.cant=mid-a+1+B.left.cant; C.left.val=A.sum+B.left.val;}
    C.right=B.right;
    if(B.right.cant==b-mid && A.right.val>0) {C.right.cant+=A.right.cant; C.right.val+=A.right.val;}
    if(B.sum+A.right.val>C.right.val) {C.right.cant=b-mid+A.right.cant; C.right.val=B.sum+A.right.val;}
    return C;
}