// Author: Expert_Dream
// Copyright (c) 2024 Expert_Dream All rights reserved.
// Problem: P3709 大爷的字符串题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3709
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Date: 2024-05-21 22:11:18

// #pragma GCC optimize(2,3,"Ofast","inline")
#include<bits/stdc++.h>
// #include <atcoder/all>
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fs first
#define sc second
#define x0 _x0_
#define y1 _y1_
#define endl '\n'
#define re register
#define pb push_back
#define vi vector<int>
#define pq priority_queue
#define mem(a,x) memset((a),(x),sizeof(a))
#define debug(x) cout<<"debug:"<<x<<endl;
#define sz(s) (int)(s.size())
#define all(a) a.begin(),a.end()
#define rd(l,r) (myrand()%(r-l+1)+l)
#define print(x) {cout<<x<<endl;return;}
#define For(x,y,z) for(int x = y;x <= z;x++)
#define For_(x,y,z) for(int x = y;x >= z;x--)
#define between(x, flo, top) (flo <= x && x <= top)
// #define double long double
using namespace std;
// using namespace atcoder;
mt19937 myrand(time(0));
template <typename Type> void get_min(Type &w1,const Type w2) { if(w2<w1) w1=w2; } 
template <typename Type> void get_max(Type &w1,const Type w2) { if(w2>w1) w1=w2; }
template <typename Type> Type up_div(Type w1,Type w2) { return (w1/w2+(w1%w2?1:0)); }
namespace FastIO {template <typename T = int>inline T read() {T s=0,w=1;char c=getchar();while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}while(isdigit(c))s=(s<<1)+(s<<3)+(c^48),c=getchar();return s*w;}template <typename T>inline void read(T &s){s=0;int w=1;char c=getchar();while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}while(isdigit(c))s=(s<<1)+(s<<3)+(c^48),c=getchar();s*=w;}template <typename T, typename... Args> inline void read(T &x, Args &...args) {read(x), read(args...);}template <typename T>inline void write(T x,char ch = '\n') {if(x<0)x=-x,putchar('-');static char stk[200];int top=0;do{stk[top++]=x%10+'0',x/=10;}while(x);while(top)putchar(stk[--top]);putchar(ch);return;}template <typename T, typename... Args> inline void write(T x, Args ...args) {write(x,' '), write(args...);}template <typename Type> void Write(vector<Type> v) {for(auto it:v)write(it,' ');puts("");}}
using namespace FastIO;
#define int long long
const int mod = 998244353,inf = 0x3f3f3f3f,N = 5e5+5,M = 1e6+5,K = 3000+5;// 1000000007
const long long linf = 0x3f3f3f3f3f3f3f3f;
int n,m;
pair<pii,int> query[N];
pii a[N];

int unq[N];
int id[N],sq;
int sum[N];
int cnt[N];
int now = 0;
void add(int y){
	int x=a[y].fs;
	sum[cnt[x]]--;
	cnt[x]++;
	sum[cnt[x]]++;
	get_max(now,cnt[x]);
}void del(int y){
	int x=a[y].fs;
	sum[cnt[x]]--;
	if(sum[cnt[x]]==0 && now == cnt[x]) now--;
	cnt[x]--;
	sum[cnt[x]]++;
}int ans[N];
int get(int x){return id[x];}
bool cmp(pair<pii,int> a,pair<pii,int> b){
	if(get(a.sc)!=get(b.sc))
		return get(a.sc)<get(b.sc);
	else 
		return a.fs.fs < b.fs.sc;
}
void solve(){
	read(n,m);
	int sq=sqrt(m);
	For(i,1,m) id[i]=(int)(i-1)/(int)sq + 1;
	For(i,1,n) read(a[i].fs),unq[i]=a[i].fs,a[i].sc=i;
	For(i,1,m)read(query[i].fs.fs,query[i].fs.sc),query[i].sc=i;
	sort(unq+1,unq+1+n);int tot = unique(unq+1,unq+1+n)-unq-1;
	For(i,1,n) a[i].fs=lower_bound(unq+1,unq+1+tot,a[i].fs)-unq;
	sort(query+1,query+m+1,cmp);	
	int l=1,r=0;
	For(i,1,m){
		int L=query[i].fs.fs,R=query[i].fs.sc;
		while(L>l)del(l++);
		while(L<l)add(--l);
		while(R>r)add(++r);
		while(R<r)del(r--);
		ans[query[i].sc] = now;
	}For(i,1,m)write(-ans[i]);
}signed main(){
	// ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T=1;
	// read(T);
	For(_,1,T) solve();
	return 0;
}