题目背景
在那遥远的西南有一所学校

/被和谐部分/

然后去参加该省省选虐场

然后某蒟蒻不会做，所以也出了一个字符串题：

题目描述
给你一个字符串a，每次询问一段区间的贡献

贡献定义：

每次从这个区间中随机拿出一个字符x，然后把x从这个区间中删除，你要维护一个集合S

如果S为空，你rp减1

如果S中有一个元素不小于x，则你rp减1，清空S

之后将x插入S

由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少rp？rp初始为0

询问之间不互相影响~

输入格式
第一行两个数n，m，表示字符串长度与询问次数

之后一行n个数，表示字符串

由于你是大爷，所以字符集1e9

之后m行每行两个数，表示询问的左右区间

输出格式
m行，每行一个数表示答案

输入输出样例
输入 #1 复制
3 3
3 3 3
3 3
3 3
3 3
输出 #1 复制
-1
-1
-1
说明/提示
前4个点1s，后面的点4s

对于10%的数据，是样例

对于另外10%的数据，n,m <= 100

对于另外10%的数据，n,m <= 1000

对于另外10%的数据，n,m <= 10000

对于另外10%的数据，n,m <= 100000

对于100%的数据，n,m <= 200000

保证数据向某省省选day1T2一样sb，大家尽情用暴力水过题吧！

没事，你只要在一个好学校，就算这题只能拿到10分，也可以进队了

题目很难读懂，大概就是问你一个区间众数出现的次数，然后加个负号。为什么呢？很容易看出，我们减少的rp，就是递增序列的个数，然后就能转化为众数问题了，因为如果两个数字不相同，那么一定能存在于同一递增序列当中，反之不存在同一递增序列，那么两数相等。 故题目就是求众数出现的次数。

这题可以离线，那么我们直接莫队就好了（分块二分太麻烦）。

我们维护每个数字出现的次数 cnt ，和出现当前次数的一共有多少个 num。一个记录当前的答案sum。

然后我们就可以区间转移了。

add：让x的出现次数增加 cnt[x]++，num[cnt[x]]++ , num[cnt[x]-1]-- ； 然后看当前的cnt[x]与当前的sum，取最大值。

del：和上面差不多，只是判断答案时，需要判断当前的cnt[x]减少之后会不会改变sum，怎么判断呢？如果当前的sum[cnt[x]]只有一个，那么减少后，答案肯定减一，否则不变。

还要注意，需要离散化一下。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,m,len,bl,a[N],b[N],cnt[N],num[N],sum,res[N],cl,cr;
struct node{
	int l,r,id;
}t[N];
int cmp(const node &s1,const node &s2){
	return (s1.l/bl==s2.l/bl)?(s1.r<s2.r):(s1.l<s2.l);
}
inline void add(int x){
	num[cnt[a[x]]++]--;	num[cnt[a[x]]]++;	sum=max(sum,cnt[a[x]]);
}
inline void del(int x){
	num[cnt[a[x]]]--;	if(cnt[a[x]]==sum&&!num[sum])	sum--;	num[--cnt[a[x]]]++;
}
signed main(){
	scanf("%d %d",&n,&m);	bl=sqrt(n);
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]),b[i]=a[i];
	for(int i=1;i<=m;i++)	scanf("%d %d",&t[i].l,&t[i].r),t[i].id=i;
	sort(b+1,b+1+n);	len=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)	a[i]=lower_bound(b+1,b+1+len,a[i])-b;
	sort(t+1,t+1+m,cmp);	cl=1;
	for(int i=1;i<=m;i++){
		int L=t[i].l;	int R=t[i].r;
		while(cl<L)	del(cl++);
		while(cl>L)	add(--cl);
		while(cr<R)	add(++cr);
		while(cr>R)	del(cr--);
		res[t[i].id]=sum;
	}
	for(int i=1;i<=m;i++)	printf("%d\n",-res[i]);
	return 0;
}