应该是我写挂了。。。

#include<bits/stdc++.h>
using namespace std;
struct Query{int id,pos;};
const int N = 2e6 + 1000, M = 1e5 + 1000;
int read() {int x;scanf("%d",&x);return x;}
vector<Query> q[M];
vector<int> G[M];
int fa[M],vis[M],n,m,root,ans[N],top,val[M],rc[M],lc[M],st[M];
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
void dfs(int x,int Fa) {
	for(auto y:G[x]) {
		if(y == Fa) continue;dfs(y,x);fa[y] = x;
	}
	vis[x] = 1;
	for(auto Q:q[x]) {
		if(vis[Q.pos]) ans[Q.id] = find(Q.pos);
	}
}
int main() {
	n = read();m = read();
	for(int i = 1;i <= n;i++) val[i] = read();
	for(int i = 1;i <= n;i++) {
		int k = top;
		while(k && val[i] >= val[st[k]]) k--;
		if(k) rc[st[k]] = i;
		if(k < top) lc[i] = st[k + 1];
		st[++k] = i;top = k;
	}
	root = st[1];
	for(int i = 1;i <= n;i++) {
		int a = lc[i],b = rc[i];
		if(a) G[i].push_back(a);
		if(b) G[i].push_back(b);
	}
	for(int i = 1;i <= m;i++) {
		int a = read(),b = read();
		q[a].push_back((Query){i,b});
		q[b].push_back((Query){i,a});
	}
	for(int i = 1;i <= n;i++) fa[i] = i;
	dfs(root,0);
	for(int i = 1;i <= m;i++) printf("%d\n", val[ans[i]]);
}