#include<bits/stdc++.h>
#define For( i , a , b ) for( register int i = ( a ) ; i <= ( b ) ; ++i )
#define Rep( i , a , b ) for( register int i = ( a ) ; i >= ( b ) ; --i )
using namespace std ;
inline int read() {
    int s = 0 ; char ch = getchar() ; bool f = 0 ;
    for( ; !isdigit( ch ) ; ch = getchar() )  f ^= !( 45 ^ ch ) ;
    for( ; isdigit( ch ) ; ch = getchar() ) s  = (  s <<  3 ) +(  s << 1 ) + (  ch ^ 48 ) ;
    if( f ) return -s; return s ;
}
const int N = 400005 , B = 444 ;
map < int , int > M ;
int a[ N ] , n , m , cnt , now , tn[ N ] , cn[ N ] , l = 1 , r = 0 ;
struct node{
    int l , r , id , ans ;
} t[ N ] ;
bool cmp( node x , node y ) {
    if( x.l / B != y.l / B ) return x.l < y.l ;
    else return ( x.l / B ) & 1 ? x.r < y.r : x.r > y.r ;
}
bool lcmp( node x , node y ) { return x.id < y.id ; }
void kill( int x ) {
    cn[ tn[ a[ x ] ] ] -- ;
    if( !cn[ now ] ) now -- ;
    tn[ a[ x ] ] -- ; cn[ tn[ a[ x ] ] ] ++ ;
}
void add( int x ) {
    cn[ tn[ a[ x ] ] ] -- ;
    tn[ a[ x ] ] ++ ;
    cn[ tn[ a[ x ] ] ] ++ ;
    now = max( now , tn[ a[ x ] ] ) ;
}
void solve( node x ) {
    while( l < x.l ) kill( l++ ) ;
    while( l > x.l ) add( --l ) ;
    while( r < x.r ) add( ++r ) ;
    while( r > x.r ) kill( r-- ) ;
}
void write( int x ) {
    if( x > 9 ) write( x / 10 ) ;
    putchar( ( x % 10 ) ^ 48 ) ;
}
int main() {
//    freopen("t.in" , "r" , stdin ) ;
//    freopen("t.out" , "w" , stdout ) ;
    memset( tn , 0 , sizeof tn ) ;
    memset( cn , 0 , sizeof cn ) ;
    n = read() ; m = read() ;
    For( i , 1 , n ) {
        a[ i ] = read() ;
        if( M[ a[ i ] ] ) a[ i ] = M[ a[ i ] ] ;
        else M[ a[ i ] ] = ++cnt , a[ i ] = cnt ;
    }
    For( i , 1 , m ) t[ i ].l = read() , t[ i ].r = read() , t[ i ].id = i , t[ i ].ans = 0 ;
    sort( t + 1 , t + 1 + m , cmp ) ;
    For( i , 1,  m ) solve( t[ i ] ) , t[ i ].ans = -now ;
    sort( t + 1 , t + 1 + m , lcmp ) ;
    For( i , 1 , m ) putchar( '-' ) , write( -t[ i ].ans ) , puts("") ;
    return 0 ;
}