#include <cstdio>

#include <algorithm>

#include <cstring>

#define N 100010

using namespace std;

int n,fa[N],m,fr[N];

//fr[x]维护猴子x所在集合在左偏树上的编号 

int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}

namespace Lt{

	int cnt,l[N],r[N],v[N],d[N];

	inline void Init(){

		cnt=0;

		memset(l,0,sizeof(l)),memset(r,0,sizeof(r));

		memset(v,0,sizeof(v)),memset(d,0,sizeof(d));

	}

	int merge(int x,int y){

		if(!x||!y) return x+y;

		if(v[x]<v[y]) swap(x,y);

		r[x]=merge(r[x],y);

		if(d[r[x]]>d[l[x]]) swap(l[x],r[x]);

		d[x]=d[r[x]]+1;

		return x;

	}

	inline void clear(int x){l[x]=r[x]=d[x]=0;}//记得一定要清零

}

inline int read(){

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int main(){

	while(~scanf("%d",&n)){

		Lt::Init();

		for(int i=1;i<=n;++i) Lt::v[i]=read(),fa[i]=fr[i]=i;

		for(m=read();m--;){

			int u=read(),v=read(),px=Find(u),py=Find(v),hhh;

			if(px==py) puts("-1");

			else{

				fa[px]=hhh=py;

				u=fr[px],v=fr[py];

				int t1=Lt::merge(Lt::l[u],Lt::r[u]),t2=Lt::merge(Lt::l[v],Lt::r[v]);

				Lt::clear(u),Lt::v[u]/=2;

				Lt::clear(v),Lt::v[v]/=2;

				t1=Lt::merge(t1,u),t2=Lt::merge(t2,v);

				int x=Lt::merge(t1,t2);

				printf("%d\n",Lt::v[x]);

				fr[hhh]=x;

			}

		}

	}

	return 0;

}