不知道为什么 MLE 了，基本上是粘的板子，应该没什么问题啊/jk

// Problem: P1456 Monkey King
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1456
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include <stdio.h>
const int maxn=100001;
int val[maxn],ch[maxn][2],dist[maxn],fa[maxn];
template<typename T>
void swap(T&a,T&b){T c=a;a=b;b=c;}
int merge(int a,int b){
    if(!a||!b||a==b)return a|b;
    if(val[a]>val[b])swap(a,b);
    ch[b][1]=merge(ch[b][1],a);
    if(dist[ch[b][0]]<dist[ch[b][1]])swap(ch[b][0],ch[b][1]);
    dist[b]=dist[ch[b][1]]+1;
    return b;
}
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
    int n,m,x,y,a,b;
    for(;~scanf("%d",&n);){
	    for(int i=1;i<=n;++i)
	        scanf("%d",val+i),dist[i]=1,fa[i]=i,ch[i][0]=ch[i][1]=0;
	    scanf("%d",&m);
	    for (;m--;){
	        scanf("%d%d",&x,&y);
	        a=find(x),b=find(y);
	        if(a==b)puts("-1");
        	else{
 	       		val[a]>>=1,x=merge(ch[a][0],ch[a][1]),x=fa[a]=fa[ch[a][0]]=fa[ch[a][1]]=merge(a,x);
        		val[b]>>=1,y=merge(ch[b][0],ch[b][1]),y=fa[b]=fa[ch[b][0]]=fa[ch[b][1]]=merge(b,y);
        		printf("%d\n",val[fa[x]=fa[y]=merge(x,y)]);
        	}
    	}
    }
    return 0;
}