#include<iostream>
#include<tuple>
using namespace std ;
#define f(i,s,n) for(int i=s;i<n;i++)
#define pii pair<int,int> 
#define ti tuple<int,int,int,int,int,int>  //maxV,maxC,lV,lC,rV,rC 
#define X first 
#define Y second
//#define DEBUG 
#define MIN -100005
#define g(i) get<i>
struct SegTree
{
    int n ;
    ti* arr ;
    SegTree(int nn)
    {
        n=nn;arr=new ti[3*n+5] ;
        //f(i,0,2*n+5) arr = make_pair(0,0) ;
        f(i,0,3*n+5) arr[i] = make_tuple(MIN,MIN,MIN,MIN,MIN,MIN) ;
    }
    ti build(int l,int r,int node,int* inp)
    {
        #ifdef DEBUG 
        cout<<"Visiting node :"<<node<<" l :"<<l<<" r :"<<r<<endl ;
        #endif 
        if(l>r) return make_tuple(MIN,MIN,MIN,MIN,MIN,MIN) ;
        if(l==r) 
        {
            #ifdef DEBUG 
            cout<<"node :"<<node<<" pos :"<<l<<" val :"<<inp[l]<<" count :"<<1<<endl ;
            #endif 
            
            return arr[node]=make_tuple(inp[l],1,inp[l],1,inp[l],1) ;
        }
        int mid = l+(r-l)/2 ;
        //return arr[node]=build(l,mid,2*node+1)+build(mid+1,r,2*node+2) ;
        ti L = build(l,mid,2*node+1,inp) ;
        ti R = build(mid+1,r,2*node+2,inp) ;
        int a,b,c,d,e,f ;
        a = b = c = d = e = f = MIN ;
        if(g(2)(L)!=g(4)(R))
        {
            c = g(2)(L) ;
            d = g(3)(L) ;
            e = g(4)(R) ;
            f = g(5)(R) ;
        }
        else 
        {
            c = e = g(2)(L) ;
            d = f = g(3)(L)+g(5)(R) ;
        }
        if(g(4)(L)==g(4)(R))
        {
            if(f<g(5)(L)+g(5)(R)) 
            {
                e = g(4)(L) ;
                f = g(5)(L)+g(5)(R) ;
            }
        }
        if(g(2)(L)==g(2)(R))
        {
            if(d<g(3)(L)+g(3)(R))
            {
                c = g(2)(L) ;
                d = g(3)(L)+g(3)(R) ;
            }
        }
        if(g(4)(L)==g(2)(R)) //matching 
        {
            b = g(5)(L)+g(3)(R) ;
            a = g(4)(L) ;
            
        }
        if(g(0)(L)==g(0)(R))
        {
            if(g(1)(L)+g(1)(R)>b) 
            {
                b = g(1)(L)+g(1)(R) ;
                a = g(0)(L) ;
            }
        }
        if(g(1)(L)>b) 
        {
            b = g(1)(L) ;
            a = g(0)(L) ;
        }
        if(g(1)(R)>b) 
        {
            b = g(1)(R) ;
            a = g(0)(R) ;
        }
        #ifdef DEBUG 
        cout<<"node :"<<node<<" : "<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<" "<<f<<endl ;
        #endif
        
        return arr[node] = make_tuple(a,b,c,d,e,f) ;
    }
    ti query(int node,int l,int r,int ql,int qr)
    {
        if(ql>r || qr<l) return make_tuple(MIN,MIN,MIN,MIN,MIN,MIN) ;
        if(ql<=l && r<=qr) 
        {
            
            #ifdef DEBUG 
            int a,b,c,d,e,f ;
            a = g(0)(arr[node]) ;
            b = g(1)(arr[node]) ;
            c = g(2)(arr[node]) ;
            d = g(3)(arr[node]) ;
            e = g(4)(arr[node]) ;
            f = g(5)(arr[node]) ;
            cout<<"(q)node :"<<node<<" : "<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<" "<<f<<endl ;
            #endif
            return arr[node] ;
        }
        int mid = l+(r-l)/2 ;
        ti L = query(2*node+1,l,mid,ql,qr) ;
        ti R = query(2*node+2,mid+1,r,ql,qr) ;
        /*if(L.Y>R.Y) return L ;
        else return R ;*/
        int a,b,c,d,e,f ;
        a=b=c=d=e=f=MIN ;
        if(g(2)(L)!=g(4)(R))
        {
            c = g(2)(L) ;
            d = g(3)(L) ;
            e = g(4)(R) ;
            f = g(5)(R) ;
        }
        else 
        {
            c = e = g(2)(L) ;
            d = f = g(3)(L)+g(5)(R) ;
        }
        if(g(4)(L)==g(4)(R))
        {
            if(f<g(5)(L)+g(5)(R)) 
            {
                e = g(4)(L) ;
                f = g(5)(L)+g(5)(R) ;
            }
        }
        if(g(2)(L)==g(2)(R))
        {
            if(d<g(3)(L)+g(3)(R))
            {
                c = g(2)(L) ;
                d = g(3)(L)+g(3)(R) ;
            }
        }
        if(g(4)(L)==g(2)(R)) //matching 
        {
            b = g(5)(L)+g(3)(R) ;
            a = g(4)(L) ;
        }
        if(g(0)(L)==g(0)(R))
        {
            if(g(1)(L)+g(1)(R)>b) 
            {
                b = g(1)(L)+g(1)(R) ;
                a = g(0)(L) ;
            }
        }
        if(g(1)(L)>b) 
        {
            b = g(1)(L) ;
            a = g(0)(L) ;
        }
        if(g(1)(R)>b) 
        {
            b = g(1)(R) ;
            a = g(0)(R) ;
        }
        #ifdef DEBUG 
        cout<<"(q)node :"<<node<<" : "<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<" "<<f<<endl ;
        #endif
        
        return make_tuple(a,b,c,d,e,f) ;

    }
    
    void deleteS()
    {
        delete[] arr ;
    }


};
int main()
{
    int n ;cin>>n ;
    ios_base::sync_with_stdio(false) ;
    cin.tie(NULL) ;
    while(n!=0)
    {
        int q ;
        cin>>q ;
        int *arr = new int[n] ;f(i,0,n) cin>>arr[i] ;
        SegTree S(n) ;
        S.build(0,n-1,0,arr) ;
        f(i,0,q) 
        {
            int a,b ;cin>>a>>b ;
            ti ans = S.query(0,0,n-1,a-1,b-1) ;
            cout<<g(1)(ans)<<endl ;
        }
        S.deleteS() ;
        delete[] arr ;
        cin>>n ;
    }
}