RT，样例都过不了

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,m,a[N],root,s[N],top,e[N],cnt,fi[N],sum[N],dep[N],B=8;
int M[1000][10][10],pre[1000][10],suf[1000][10],Min[30005],ST[30005][25];
int typ[N],Sum[N],lg[N]; 
struct T {
	int val,l,r;
} t[N];
vector<int>ve[N];
void build1() {
	for(int i=1; i<=n; i++) {
		t[i].val=a[i],s[top+1]=0;
		while(top&&t[s[top]].val<a[i])top--;
		t[i].l=s[top+1];
		if(top)t[s[top]].r=i;
		s[++top]=i;
	}
	root=s[1];
}
void build2() {
	int num[1005];
	while(cnt&7)cnt++;
	for(int i=0; i<(1<<(B-1)); i++) {
		num[1]=0;
		for(int j=0; j<B-1; j++) {
			if(i&(1<<j))num[j+2]=num[j+1]+1;
			else num[j+2]=num[j+1]-1;
		}
		for(int j=1;j<=B;j++){
			M[i][j][j]=j;
			for(int k=j+1;k<=B;k++)	M[i][j][k]=num[k]<num[M[i][j][k-1]]?k:M[i][j][k-1];
		}
		for(int j=1;j<=B;j++)pre[i][j]=M[i][1][j],suf[i][j]=M[i][j][B];
		Min[i]=M[i][1][B];
	}
	for(int i=1;i<=(cnt>>3);i++){
		typ[i]=0;
		for(int j=(i<<3)-B+2,t=0;j<=(i<<3);j++,t++)
			if(sum[j]-sum[j-1]>=0)typ[i]|(1<<t);
		Sum[i]=sum[Min[typ[i]]+((i-1)<<3)];
	}
	for(int i=1;i<=(cnt>>3);i++)ST[i][0]=i;
	int len=lg[cnt]-2;
	for(int j=1;j<=len;j++){
		for(int i=1;i<=(cnt>>3)-(1<<j)+1;i++){
			int k=i+(1<<(j-1));
			ST[i][j]=Sum[ST[k][j-1]]<Sum[ST[i][j-1]]?ST[k][j-1]:ST[i][j-1];
		}
	}
}
int Brmq(int l,int r){
	int k=lg[r-l+1];
	r-=(1<<k)-1;
	return Sum[ST[l][k]]<Sum[ST[r][k]]?ST[l][k]:ST[r][k];
}
void dfs(int now) {
	e[++cnt]=now;
	fi[now]=cnt;
	for(int i=0; i<ve[now].size(); i++) {
		int y=ve[now][i];
		dep[y]=dep[now]+1;
		dfs(y);
		e[++cnt]=now;
	}
}
int query(int l,int r) {
	if(l>r)swap(l,r); 
	int L=(l-1)/B+1,R=(r-1)/B+1;
	if(L==R){
		int pos=(L-1)<<3;
		return pos+M[typ[L]][l-pos][r-pos];
	}
	else if(L+1==R){
		int pl=(L-1)<<3,pr=(R-1)<<3;
		return sum[suf[typ[L]][l-pl]+pl]<sum[pre[typ[R]][r-pr]+pr]?suf[typ[L]][l-pl]+pl:pre[typ[R]][r-pr]+pr; 
	}
	else{
		int pl=(L-1)<<3,pr=(R-1)<<3;
		int t1=Brmq(L+1,R-1),t2=sum[suf[typ[L]][l-pl]+pl]<sum[pre[typ[R]][r-pr]+pr]?suf[typ[L]][l-pl]+pl:pre[typ[R]][r-pr]+pr;
		t1=((t1-1)<<3)+Min[typ[t1]];
		return sum[t1]<sum[t2]?t1:t2;
	}
}
int LCA(int x,int y) {
	return e[query(fi[x],fi[y])];
}
int main() {
	cin>>n>>m;
	for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
	for(int i=1; i<=n; i++)cin>>a[i];
	build1();
	for(int i=1; i<=n; i++) {
		if(t[i].l)ve[i].push_back(t[i].l);
		if(t[i].r)ve[i].push_back(t[i].r);
	}
	dfs(root);
	for(int i=1; i<=cnt; i++)sum[i]=dep[e[i]];
	build2();
	int l,r;
	while(m--) {
		cin>>l>>r;
		cout<<a[LCA(l,r)]<<endl;
	}
}