#include<bits/stdc++.h>

#define Int  long long int
#define usInt  unsigned Int
#define min(a,b)  (a<b?a:b)
#define max(a,b)  (a>b?a:b)

using std::cin;using std::cout;

int n,m;
class Monkey{
    public:
        int strength;
        Monkey* bro;Monkey* son;
        Monkey* boss;
        void half();
        Monkey* merge_bros();
        
    public:Monkey(){bro=nullptr,son=nullptr,boss=this;}
};
Monkey* s[100005];
Monkey* merge_Monkey(Monkey* a,Monkey* b);

int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;++i){
            s[i]=new Monkey();
            scanf("%d",&(s[i]->strength));
        }
        scanf("%d",&m);
        for(int u,v;~--m;){
            scanf("%d%d",&u,&v);
            s[u]->half();s[v]->half();
            printf("%d\n",merge_Monkey(s[u],s[v])->strength);
        }
        for(int i=1;i<=n;++i){
            delete(s[i]);
        }
    }
    return 0;
}

Monkey* merge_Monkey(Monkey* a,Monkey* b){
    if(a!=nullptr)while(a!=a->boss)a=a->boss;if(b!=nullptr)while(b!=b->boss)b=b->boss;
    if(a==b){
        Monkey* o=new Monkey;
        o->strength=-1;
        return o;
    }
    if(a==nullptr)return b;
    if(b==nullptr)return a;
    if(a->strength<b->strength)std::swap(a,b);
    b->bro=a->son;
    a->son=b;
    b->boss=a;
    return a;
}
Monkey* Monkey::merge_bros(){
    this->boss=this;Monkey* a=this->bro;
    if(a==nullptr)return this;a->boss=a;Monkey* b=a->bro;
    this->bro=nullptr;a->bro=nullptr;
    this->boss=merge_Monkey(this,a)->boss;
    if(b!=nullptr)this->boss=merge_Monkey(this->boss,b->merge_bros())->boss;
    return this->boss;
}
void Monkey::half(){
    Monkey* bss=this->boss;
    while(bss!=bss->boss)bss=bss->boss;
    Monkey* t=bss->son;
    bss->son=nullptr;
    bss->strength/=2;
    if(t!=nullptr){
        bss->boss=merge_Monkey(bss,t->merge_bros())->boss;
    }
}

https://www.luogu.com.cn/record/75074100