FrequentValues_SPOJ

//In the Name of Allah Most Gracious, Most Merciful//
/*If you want something you've never had, you have  to do something you never did.*/

#include<bits/stdc++.h>
using namespace std;


#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define M 100007
#define INF 1e9
#define INFL 1e18
#define PI acos(-1)
#define mp make_pair
#define fast_in_out ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//const int fx[]= {+1,-1,+0,+0};
//const int fy[]= {+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
int arr[100100];

struct data
{
    int leftval;
    int leftfreq;
    int rightval;
    int rightfreq;
    int maxval;
    int maxfreq;
}tree[4*100010];



data combine(data d1,data d2)
{
    if(d1.leftval==d2.rightval)
    {
        data ans;
        ans.leftval=d1.leftval;
        ans.leftfreq=d1.maxfreq+d2.maxfreq;
        ans.rightfreq=d1.maxfreq+d2.maxfreq;
        ans.rightval=d2.rightval;
        ans.maxfreq=d1.maxfreq+d2.maxfreq;
        ans.maxval=d1.leftval;
     //   cout<<ans.maxval<<" "<<ans.maxfreq<<endl;
        return ans;
    }
    else if(d1.leftval==d2.leftval)
    {
        data ans;
        ans.leftval=d1.leftval;
        ans.leftfreq=d1.leftfreq+d2.leftfreq;
        ans.rightfreq=d2.rightfreq;
        ans.rightval=d2.rightval;
        if(d1.leftfreq+d2.leftfreq>=d2.rightfreq && d1.leftfreq+d2.leftfreq>=d2.maxfreq)
        {
            ans.maxfreq=d1.leftfreq+d2.leftfreq;
            ans.maxval=d1.leftval;
        }
        else if(d2.rightfreq>=d2.maxfreq)
        {
            ans.maxfreq=d2.rightfreq;
            ans.maxval=d2.rightval;
        }
        else
        {
            ans.maxfreq=d2.maxfreq;
            ans.maxval=d2.maxval;
        }

        return ans;
    }

     else if(d1.rightval==d2.rightval)
    {
         data ans;
        ans.leftval=d1.leftval;
        ans.leftfreq=d1.leftfreq;
        ans.rightfreq=d1.rightfreq+d2.maxfreq;
        ans.rightval=d2.rightval;
        if(d2.maxfreq+d1.rightfreq>=d1.leftfreq && d2.maxfreq+d1.rightfreq>=d1.maxfreq)
        {
            ans.maxfreq=d2.maxfreq+d1.rightfreq;
            ans.maxval=d2.rightval;
        }
        else if(d1.leftfreq>=d1.maxfreq)
        {
            ans.maxfreq=d1.leftfreq;
            ans.maxval=d1.leftval;
        }
        else
        {
            ans.maxfreq=d1.maxfreq;
            ans.maxval=d1.maxval;
        }

        return ans;
    }

    else if(d1.rightval==d2.leftval)
    {
       data ans;
        ans.leftval=d1.leftval;
        ans.leftfreq=d1.leftfreq;
        ans.rightfreq=d2.rightfreq;
        ans.rightval=d2.rightval;
        if(d2.leftfreq+d1.rightfreq>=d1.maxfreq && d2.leftfreq+d1.rightfreq>=d2.maxfreq)
        {
            ans.maxfreq=d2.leftfreq+d1.rightfreq;
            ans.maxval=d2.leftval;
        }
        else if(d1.maxfreq>=d2.maxfreq)
        {
            ans.maxfreq=d1.maxfreq;
            ans.maxval=d1.maxval;
        }
        else
        {
            ans.maxfreq=d2.maxfreq;
            ans.maxval=d2.maxval;
        }
        return ans;
    }


    else
    {
         data ans;
        ans.leftval=d1.leftval;
        ans.leftfreq=d1.leftfreq;
        ans.rightfreq=d2.rightfreq;
        ans.rightval=d2.rightval;
        if(d1.maxfreq>=d2.maxfreq)
        {
         ans.maxfreq=d1.maxfreq;
          ans.maxval=d1.maxval;
        }
        else
        {
          ans.maxfreq=d2.maxfreq;
          ans.maxval=d2.maxval;
        }
        return ans;
    }
}
void build(int node,int b,int e)
{
    if(b==e)
    {
//        cout<<arr[b]<<endl;
        data d;
//        cout<<node<<" "<<arr[b]<<endl;
        d.leftfreq=1;
        d.leftval=arr[b];
        d.rightfreq=1;
        d.rightval=arr[b];
        d.maxfreq=1;
        d.maxval=arr[b];
        tree[node]=d;
        return;
    }
    int left=node*2;
    int right=node*2+1;
    int mid=(b+e)/2;
    build(left,b,mid);
    build(right,mid+1,e);
    tree[node]=combine(tree[left],tree[right]);
}



data query(int node,int b,int e,int i,int j)
{
    if(i>e || j<b)
    {
    data zero;
    zero.maxfreq=0;
    zero.leftfreq=0;
    zero.leftval=INF;
    zero.maxval=INF;
    zero.rightval=INF;
    zero.rightfreq=0;
        return zero;
    }
    if(b>=i & e<=j)
    {
        return tree[node];
    }
    int left=node*2;
    int right=node*2+1;
    int mid=(b+e)/2;
    data q1=query(left,b,mid,i,j);
    data q2=query(right,mid+1,e,i,j);
    data q=combine(q1,q2);
    return q;
}
int main()
{
    fast_in_out;
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n,q;
    while(true)
    {
    cin>>n;
    if(n==0)
    {
        break;
    }
    cin>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    build(1,1,n);
//    for(int i=20;i>=1;i--)
//    {
//        cout<<i<<" "<<tree[i].maxval<<endl;
//    }
   // cout<<tree[1].maxfreq<<endl;
   while(q--)
   {
       int x,y;
       cin>>x>>y;
       data ans=query(1,1,n,x,y);
       cout<<ans.maxfreq<<endl;
   }
    data zero;
    zero.maxfreq=0;
    zero.leftfreq=0;
    zero.leftval=INF;
    zero.maxval=INF;
    zero.rightval=INF;
    zero.rightfreq=0;
    for(int i=0;i<400000;i++)
    {
        if(i<=100000)
        {
            arr[i]=0;
        }
        tree[i]=zero;
    }


    }
   return 0;
}