我 是 傻 逼。
先不管那个限制。如果有一个序列 \(a\)，怎么求答案？
假设我们一个一个减，那么答案就是序列长度；但是，我们不一定会一个一个减：如果有 \(x<y,a_x=a_y=k\)，且 \(x+1,y-1\) 之间没有不大于 \(k\) 的数，那么我们可以把它们放在一起操作，答案会减少 1。现在问题就转变为了数这样的 \((x,y)\) 的数量。
现在我们加上题目中的限制：考虑把询问离线，挂到右端点，从小到大枚举右端点 \(r\)，同时加入 \(a_i=r\) 的数。如果我们只考虑 \([1,r]\) 间的数，定义满足 \(p\in[x+1,y-1]\)，且 \(a_p\le r,a_p<a_x\) 的所有 \(p\) 中最大的那个 \(a_p=t\)，那么 \((x,y)\) 会对答案产生 -1 的贡献当且仅当询问的左区间 \(l\) 满足 \(l\ge t\)。
同时，你还会发现随着 \(r\) 增大，一个数对 \((x,y)\) 对应的 \(t\) 是不变的，所以我们只用在 \(a_x=a_y=r\) 的时候求一下。这个维护起来很简单，直接线段树/树状数组维护一下就行。
但是如果你直接做还会有一点问题：在计算 -1 的贡献时，可能存在 \((x,y)\) 满足 \(a_x<l\)，此时显然我们不应该管他，但是这会让答案减一，因为我们分辨不出来。怎么办？我们可以反过来，假设每种存在的数我们都可以同时减，然后如果有 \(l<t\) 则答案加一，这样有 \(l<t<a_x\)，故一定合法。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,a[1000005],ql[1000005],qr[1000005];vector<int>v[1000005],Q[1000005];
struct segtree{
#define ls p<<1
#define rs p<<1|1
#define lson l,mid,ls
#define rson mid+1,r,rs
struct Node{
int s,ma;
}c[4000005];
void pushup(int p){
c[p].s=c[ls].s+c[rs].s;
c[p].ma=max(c[ls].ma,c[rs].ma);
}
void build(int l,int r,int p){
if(l==r){c[p].s=c[p].ma=0;return;}
int mid=(l+r)>>1;
build(lson),build(rson);
pushup(p);
}
void update(int l,int r,int p,int x,int k){
if(l==r){c[p].s=c[p].ma=k;return;}
int mid=(l+r)>>1;
if(x<=mid)update(lson,x,k);
else update(rson,x,k);
pushup(p);
}
int query(int l,int r,int p,int L,int R){
if(L>R)return 0;
if(L<=l&&r<=R)return c[p].ma;
int mid=(l+r)>>1,res=-inf;
if(L<=mid)res=max(res,query(lson,L,R));
if(R>mid)res=max(res,query(rson,L,R));
return res;
}
int ask(int l,int r,int p,int L,int R){
if(L>R)return 0;
if(L<=l&&r<=R)return c[p].s;
int mid=(l+r)>>1,res=0;
if(L<=mid)res+=ask(lson,L,R);
if(R>mid)res+=ask(rson,L,R);
return res;
}
#undef ls
#undef rs
#undef lson
#undef rson
}Tr;
struct BIT{
int c[1000005];
void clear(){
for(int i=1;i<=n;i++)c[i]=0;
}
void add(int x,int y){
for(;x<=n;x+=x&-x)c[x]+=y;
}
void add(int l,int r,int k){
if(l>r)return;
add(l,k);add(r+1,-k);
}
int ask(int x){
int res=0;
for(;x;x-=x&-x)res+=c[x];
return res;
}
}res;
int ans[1000005],s[1000005];
void solve(){
n=read(),m=read();
for(int i=1;i<=n;i++)v[i].clear(),Q[i].clear();
for(int i=1;i<=n;i++)a[i]=read(),v[a[i]].push_back(i);
for(int i=1;i<=m;i++)ql[i]=read(),qr[i]=read(),Q[qr[i]].push_back(i);
Tr.build(1,n,1);res.clear();
for(int r=1;r<=n;r++){
s[r]=s[r-1]+((int)v[r].size()>0);
for(int i=0;i<(int)v[r].size();i++)Tr.update(1,n,1,v[r][i],r);
for(int i=0;i<(int)v[r].size()-1;i++)res.add(1,Tr.query(1,n,1,v[r][i]+1,v[r][i+1]-1),1);
for(int i=0;i<(int)Q[r].size();i++)ans[Q[r][i]]=s[r]-s[ql[Q[r][i]]-1]+res.ask(ql[Q[r][i]]);
}
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
}
signed main(){
int T=1;
while(T--)solve();
return 0;
}