RT.

区间众数，这不就是蒲公英！直接开冲！

然后 MLE 了。

具体做法：离散化，然后处理 $s_{i,j}$ 表示第 $1 \sim i$ 块中 $j$ （离散化后）这个值出现的次数， $p_{i,j}$ 表示第 $i \sim j$ 块的众数的出现次数。

以下是代码：

#include<bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long int ll;
typedef pair<int,int> PII;

const int N = 200010;
const int M = 450;
const int INF = 0x3f3f3f3f;

bool s1;
int n,q,B,mx,c;
int a[N];
vector<int> v;
int s[M][N];
int p[M][M];
int tmp[N],tim[N],idx;
bool s2;

int gid(int x)
{
	return (x-1)/B+1;
}

int gl(int id)
{
	return (id-1)*B+1;
}

int gr(int id)
{
	return min(n,id*B);
}

int smq(int l,int r)
{
	int res=0;
	for(int i=l;i<=r;i++)
	{
		if(tim[a[i]]!=idx)
		{
			tim[a[i]]=idx;
			tmp[a[i]]=0;
		}
		tmp[a[i]]++;
		res=max(res,tmp[a[i]]);
	}
	return res;
}

int query(int l,int r)
{
	int lid=gid(l),rid=gid(r);
	if(lid==rid)
	{
		return smq(l,r);
	}
	else
	{
		int res=p[lid+1][rid-1];
		for(int i=l;i<=gr(lid);i++)
		{
			if(tim[a[i]]!=idx)
			{
				tim[a[i]]=idx;
				tmp[a[i]]=0;
			}
			if(!tmp[a[i]])
			{
				tmp[a[i]]=s[rid-1][a[i]]-s[lid][a[i]];
			}
			tmp[a[i]]++;
			res=max(res,tmp[a[i]]);
		}
		for(int i=gl(rid);i<=r;i++)
		{
			if(tim[a[i]]!=idx)
			{
				tim[a[i]]=idx;
				tmp[a[i]]=0;
			}
			if(!tmp[a[i]])
			{
				tmp[a[i]]=s[rid-1][a[i]]-s[lid][a[i]];
			}
			tmp[a[i]]++;
			res=max(res,tmp[a[i]]);
		}
		return res;
	}
}

int main()
{
	//start your program!
	cerr<<(&s2-&s1)/1024.0/1024.0<<endl;
	scanf("%d%d",&n,&q);
	B=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		v.pb(a[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
		int id=gid(i);
		s[id][a[i]]++;
		c=max(c,a[i]);
		mx=max(mx,id);
	}
	for(int i=1;i<=mx;i++)
	{
		for(int j=1;j<=c;j++)
		{
			s[i][j]=s[i-1][j]+s[i][j];
		}
	}
	for(int i=1;i<=mx;i++)
	{
		idx++;
		int res=0;
		for(int j=i;j<=mx;j++)
		{
			int L=gl(j),R=gr(j);
			for(int k=L;k<=R;k++)
			{
				if(tim[a[k]]!=idx)
				{
					tmp[a[k]]=0;
					tim[a[k]]=idx;
				}
				tmp[a[k]]++;
				res=max(res,tmp[a[k]]);
			}
			p[i][j]=res;
		}
	}
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		idx++;
		printf("%d\n",-query(l,r)); 
	}
	return 0;
}