#include<iostream>#include<cstring>#include<cstdio>using namespace std;struct node{int lson,rson;int dis;int val;}pool[110000];int root[110000];int fa[110000];int dis(int a){return a==-1?-1:pool[a].dis;}int find(int x){if(fa[x]==x) return x;fa[x]=find(fa[x]);root[x]=root[fa[x]];return fa[x];}void clean(int root){pool[root].lson=pool[root].rson=-1;pool[root].dis=0;}int merge(int a,int b){if(a==-1) return b;if(b==-1) return a;if(pool[a].val < pool[b].val) swap(a,b);if(pool[a].rson==-1) pool[a].rson=b;else pool[a].rson=merge(pool[a].rson,b);if(dis(pool[a].lson) < dis(pool[a].rson)) swap(pool[a].lson,pool[a].rson);pool[a].dis=dis(pool[a].rson)+1;return a;}int updata(int root){int ret=merge(pool[root].lson,pool[root].rson);clean(root);pool[root].val/=2;ret=merge(ret,root);return ret;}void init(int n){for(int i=0;i<n;i++){fa[i]=i;root[i]=i;clean(root[i]);}}int main(){int n,m;while(scanf("%d",&n)!=EOF){init(n);for(int i=0;i<n;i++) scanf("%d",&(pool[root[i]].val));scanf("%d",&m);int u,v;while(m--){scanf("%d %d",&u,&v);u--,v--;u=find(u);v=find(v);if(u==v){puts("-1");continue;}root[u]=updata(root[u]);root[v]=updata(root[v]);root[u]=root[v]=merge(root[u],root[v]);printf("%dn",pool[root[u]].val);fa[u]=find(v);}}}
