MAX FREQUENCY IN THE RANGE

                                           

FREQUENT - Frequent values

You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , ... , aj.

Input Specification

The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , ... , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query.

The last test case is followed by a line containing a single 0.

Output Specification

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

Sample Input

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

Sample Output

1
4
3

------------------------------------EDITORIAL--------------------------------------------------------

IN   THIS QUESTION EACH NODE  OF THE SEGMENT TREE CONTAINS  5 VALUE 

struct node
 {
   lli pf;
   lli pfv;
   lli sf;
   lli sfv;
   lli best;
}  seg[1000000];

LET US CONSIDER RANGE 0-6 

HERE PF WILL CONTAIN THE  VALUE OF ARR[0].. PFV WILL CONTAIN COUNT OF FREQUENCY  IF ELEMENT is PF IE ARR[0]

HERE SF WILL CONTAIN THE  VALUE OF ARR[6].. SFV WILL CONTAIN COUNT OF FREQUENCY  IF ELEMENT is  SF IE ARR[6]
BEST WILL CONTAIN BEST ANS IN THIS RANGE ..
NOW SINCE  RANGE IS SHORTED SOO  IT EASY TO  BUILD  SEGMENT ARRAY ..
// more explanation  is in the code 
#include<iostream>
using namespace std;
typedef  int lli;
lli arr[1000000];
int qs,qe;
#include<bits/stdc++.h>
#define inf 10000007
long long int read_int(){
 char r;
 bool start=false,neg=false;
 long long int ret=0;
 while(true){
  r=getchar();
  if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
   continue;
  }
  if((r-'0'<0 || r-'0'>9) && r!='-' && start){
   break;
  }
  if(start)ret*=10;
  start=true;
  if(r=='-')neg=true;
  else ret+=r-'0';
 }
 if(!neg)
  return ret;
 else
  return -ret;
}
struct node
 {
   lli pf;
   lli pfv;
   lli sf;
   lli sfv;
   lli best;
}  seg[1000000];
 node blank;
  
  void build(int index,int start,int end)
   
   {
    
     if(start>end) return ;
      // IF ELEMENT IS LEAF NODE 
     if(start==end)
      {
       
       
       
       seg[index].pf=arr[start];
       seg[index].sf=arr[start];
       seg[index].pfv=1;// all count =1 sinse only 1 element 
       seg[index].sfv=1;
       seg[index].best=1;
  
    return;
      }
      
     
      
         build(2*index,start,(start+end)/2);
         build(2*index+1,(start+end)/2+1,end);
         // setting fields of parrent node of segement tree with helf of childs
        seg[index].pf=seg[2*index].pf;// always since in range  start to end  pf comes from left child 
        seg[index].pfv=seg[2*index].pfv;// value of frequency of pf  must be atleast  value of frequencies in left chlild
 //  since array is shorted  soo if prefix of left sub tree ==  prefix of right sub tree than it is sure that all element in left sub array 
 // is same  and since it is matching with rights pf so value of pf of parent = sum of pfv co left and right child ... 
        if(seg[2*index].pf==seg[2*index+1].pf) seg[index].pfv+=seg[2*index+1].pfv;
        
        
        // similar concept applied of sf and sfv
         seg[index].sf=seg[2*index+1].sf;
         seg[index].sfv=seg[2*index+1].sfv;
         if(seg[2*index+1].sf==seg[2*index].sf) seg[index].sfv+=seg[2*index].sfv;
         
         
          // for best in could be either best of left sub tree or best of right sub tree or if  suffix sf  of left subtree == prefix pf
    //  right sub tree thanbest can be the sum of  sfv left sub tree + pfv of right subtree..
         seg[index].best=max(seg[2*index].best,seg[2*index+1].best);
        if(seg[2*index].sf==seg[2*index+1].pf) seg[index].best=max(seg[index].best,seg[2*index+1].pfv+seg[2*index].sfv);
          
         
      
   }
  node query(int index,int start,int end)
    {
//        cout<<qs<<" "<<qe<<endl;
//  cout<<start<<" "<<end<<endl;
  if(start>end || start>qe || end<qs) 
  {
   //cout<<blank.best<<endl;
//   cout<<" for "<<start<<" "<<end<<endl;
     return blank;
     }
         if(start>=qs && end<=qe)
          {
           return seg[index];
          }
          
          // node  for returning is created same as in case of build of parent segment node ..
          node node1=query(2*index,start,(start+end)/2);
          node node2=query(2*index+1,(start+end)/2+1,end);
          
          node ans;
           ans.pf=node1.pf;
           ans.pfv=node1.pfv;
           if(node1.pf==node2.pf) ans.pfv+=node2.pfv;
           
           ans.sf=node2.sf;
           ans.sfv=node2.sfv;
           if(node2.sf==node1.sf) ans.sfv+=node1.sfv;
           
            ans.best=max(node1.best,node2.best);
            if(node1.sf==node2.pf) ans.best=max(ans.best,node2.pfv+node1.sfv);
           return ans;
 }
int main()
 {
  int n,q ;
   blank.pf=-inf;
    blank.pfv=0;
   blank.sf=-inf;
   blank.sfv=0;
   blank.best=0;
   
   while(1)
   {
        n=read_int();
      if(n==0) break;
        q=read_int();
    for(int i=0;i<n;i++) arr[i]=read_int(); //scanf("%lld",&arr[i]);//cin>>arr[i];
     build(1,0,n-1);
      /* for(int i=1;i<=9;i++)
        {
          cout<<i<<" "<<seg[i].pf<<" "<<seg[i].pfv<<" "<<" "<<seg[i].best<<" "<<seg[i].sfv<<" "<<seg[i].sf<< endl;
        }*/
       while(q--)
        {
        
         //  cin>>qs>>qe;
        // scanf("%lld %lld ",&qs,&qe);
            qs=read_int();
            qe=read_int();
           qs-=1;
           qe-=1;
         //  node  final=query(1,0,n-1);
           node final ;
            cout<<final.best<<endl;
        }
   }
   
  return 0;
 }