它**的，T死我了！

#include<bits/stdc++.h>
using namespace std;

struct node{
	int a,l,r,len,fa;
	node(){
		l=r=fa=-1;
		len=0;
	}
}ver[100005];

int n,m;

int Find(int now){
	return ver[now].fa==-1?now:Find(ver[now].fa);
}

void swt(int now){
	int nl=ver[now].l,nr=ver[now].r;
	ver[now].len=(nl==-1||nr==-1)?0:(min(ver[nl].len,ver[nr].len)+1);
	if(nl==-1)return;
	if(nl==-1&&nr!=-1)swap(ver[now].l,ver[now].r);
	else if(ver[nl].len<ver[nr].len)swap(ver[now].l,ver[now].r);
}

int combine(int xx,int yy){
	if(xx==-1&&yy==-1)return-1;
	if(xx==-1||yy==-1)return xx+yy+1;
	if(ver[xx].a<ver[yy].a)swap(xx,yy);
	if(ver[xx].r==-1){
		ver[xx].r=yy;
		ver[yy].fa=xx;
	}
	else{
		int sn=combine(ver[xx].r,yy);
		ver[xx].r=sn;
		ver[sn].fa=xx;
	}
	swt(xx);
	return xx;
}

int del(int now){
	int nl=ver[now].l,nr=ver[now].r;
	ver[nl].fa=ver[nr].fa=-1;
	int nn=combine(nl,nr);
	ver[now].l=ver[now].r=-1;
	ver[now].len=0;
	return nn;
}

int add(int to,int now){
	return combine(to,now);
}

void clear_and_input(){
	for(int i=1;i<=n;i++){
		ver[i]=node();
		scanf("%d",&ver[i].a);
	}
}

void ask_and_answer(){
	while(m--){
		int xx,yy,fx,fy,nx,ny;
		scanf("%d%d",&xx,&yy);
		fx=Find(xx);
		fy=Find(yy);
		if(fx==fy){
			printf("-1\n");
			continue;
		}
		ver[fx].a/=2;
		ver[fy].a/=2;
		nx=add(del(fx),fx);
		if(nx!=-1)fx=nx;
		ny=add(del(fy),fy);
		if(ny!=-1)fy=ny;
		printf("%d\n",ver[combine(fx,fy)].a);
	}
}

int main(){
	while(scanf("%d",&n)!=EOF){
		clear_and_input();
		scanf("%d",&m);
		ask_and_answer();
	}
	return 0;
}