神秘好题。

首先一个贪心就是能删就删，没啥问题。

看到区间想法很多，数据结构维护或者是差分是比较容易想到的。

因为没有修改并且操作相对简单，所以优先考虑差分。

设 $f_i$ 为前缀 $1 \sim i$ 删完之后剩余的长度，我们所要求的能用 $f_r$ 和 $f_{l-1}$ 相减得到吗？

明显不可以。

难道我们只能转身投入数据结构的怀抱吗？好像没那么好维护啊。

那你可以去别的题解进行学习了，我们继续考虑差分。

对于一段区间 $[l,r]$，认为最后保留下来的一段是 $B$。如果 $B$ 的开头无法和 $c_{l-1}$ 消除，那么这种时候直接差分是对的。

那么如果可以消除呢？

这个时候你发现我们还要算上消除掉的代价。

欸，是不是对称的，可以马拉车？

明显错了，因为可能出现局部消除后的对称情况。例如 1 2 2 4 3 3 4 1 把 2 2 消除之后才是关于 3 | 3 对称的。

那好像还是有点完蛋，要不我们还是把栈和前缀拿回来吧。

这种情况下，我们记录当前前缀的答案序列，对于这么一个序列，我们发现每次在最后增加一个元素，产生的长度变化是 $\pm 1$ 的。

这个东西可以理解成是新建和回退，此时对于 $[l,r]$ 的答案，其实就是 $f_{l-1}$ 到 $f_r$ 的回退步数和新建步数之和……吗？

为啥又错了，因为你会发现 $[l,r]$ 内部形如 1 1 的东西会算重。

难道还需要神秘容斥？

我们考虑这个算重是不是和算路径长度时 $s \to x \to a \to x \to t$ 一样，对吧。那不如建图试一下。

由上文回退、新建带来的变化可知，形成的结构是一棵树，每次的回退、新建都可以理解为是指针在树上的移动。

事已至此情况就清晰了，我们要求的东西就转化成了 $l-1,r$ 对应在树上的位置的距离。

树上两点间距离随便做了，难点在于从一堆可疑的方向中找到这样一个简便做法。

时间复杂度 $O(n \log n)$，理论优化到 $O(n)$，但都 $\le10^6,2\text{s}$ 了，也没太大必要降了，常数毕竟也不大。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int c[1000005];
int fa[1000005];
int now;
int col[1000005];
int id;

int pos[1000005];
map<int,int>son[1000005];

struct node{
	int nex,to;
}e[2000005];
int tot;
int he[1000005];
inline void add(int x,int y){
	e[++tot].nex=he[x];
	e[tot].to=y;
	he[x]=tot;
	return;
}
int dep[1000005];
int f[1000005][21];

inline void dfs(int x){
	dep[x]=dep[fa[x]]+1;
	f[x][0]=fa[x];
	for (int i=1;i<21;i++){
		f[x][i]=f[f[x][i-1]][i-1];
	}
	for (int i=he[x];i;i=e[i].nex){
		int v=e[i].to;
		dfs(v);
	}
	return;
}
inline int lca(int x,int y){
	if (dep[x]<=dep[y]){
		swap(x,y);
	}
	for (int i=20;i>=0;i--){
		if (dep[f[x][i]]>=dep[y]){
			x=f[x][i];
		}
	}
	if (x==y){
		return x;
	}
	for (int i=20;i>=0;i--){
		if (f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	col[0]=-1;
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		cin>>c[i];
		if (now && col[now]==c[i]){
			now=fa[now];
			pos[i]=now;
		}
		else{
			if (son[now][c[i]]){
				now=son[now][c[i]];
			}
			else{
				son[now][c[i]]=++id;
				fa[id]=now;
				now=son[now][c[i]];
				col[now]=c[i];
			}
			pos[i]=now;
		}
	}
	for (int i=1;i<=id;i++){
		add(fa[i],i);
	}
	dfs(0);
	while (m--){
		int x,y;
		cin>>x>>y;
		x--;
		x=pos[x];
		y=pos[y];
		int l=lca(x,y);
		cout<<dep[x]+dep[y]-2*dep[l]<<"\n";
	}
	return 0;
}