#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const maxn=1e5+;

int n,m,s[maxn],rt[maxn],ls[maxn],rs[maxn],dis[maxn];

int find(int x){while(rt[x])x=rt[x]; return x;}

int merge(int x,int y)

{

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

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

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

    rt[rs[x]]=x;

    if(dis[ls[x]]<dis[rs[x]])swap(ls[x],rs[x]);

    if(rs[x])dis[x]=dis[rs[x]]+;

    else dis[x]=;

//    rt[rs[x]]=rt[ls[x]]=x;

    return x;

}

void clr(int x){rt[x]=; rs[x]=; ls[x]=;}

int main()

{

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

    {

        for(int i=;i<=n;i++)scanf("%d",&s[i]),ls[i]=rs[i]=dis[i]=rt[i]=;

        scanf("%d",&m);

        for(int i=,x,y,u,v,t1,t2;i<=m;i++)

        {

            scanf("%d%d",&x,&y);

            u=find(x); v=find(y);

            if(u==v){printf("-1\n"); continue;}

            rt[ls[u]]=; rt[rs[u]]=; rt[ls[v]]=; rt[rs[v]]=; //!

            t1=merge(ls[u],rs[u]);

            t2=merge(ls[v],rs[v]);

            clr(u); clr(v);//!

            s[u]>>=; s[v]>>=;

            merge(u,t1); merge(v,t2);

            printf("%d\n",s[merge(find(u),find(v))]);//find()

        }

    }

    return ;

}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const maxn=1e5+;

int n,m,s[maxn],rt[maxn],ls[maxn],rs[maxn],dis[maxn];

int find(int x){return rt[x]==x?x:rt[x]=find(rt[x]);}

int merge(int x,int y)

{

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

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

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

    rt[rs[x]]=x;

    if(dis[ls[x]]<dis[rs[x]])swap(ls[x],rs[x]);

    if(rs[x])dis[x]=dis[rs[x]]+;

    else dis[x]=;

//    rt[rs[x]]=rt[ls[x]]=x;

    return x;

}

int del(int x)

{

    int l=ls[x],r=rs[x];

    rt[l]=l; rt[r]=r;

    ls[x]=rs[x]=dis[x]=;

    return merge(l,r);

}

int main()

{

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

    {

        for(int i=;i<=n;i++)scanf("%d",&s[i]),rt[i]=i,ls[i]=rs[i]=dis[i]=;

        scanf("%d",&m);

        for(int i=,x,y,u,v,t1,t2;i<=m;i++)

        {

            scanf("%d%d",&x,&y);

            u=find(x); v=find(y);

            if(u==v){printf("-1\n"); continue;}

            s[u]>>=; t1=del(u),t1=merge(u,t1);

            s[v]>>=; t2=del(v),t2=merge(v,t2);

            printf("%d\n",s[merge(t1,t2)]);//find()

        }

    }

    return ;

}