/*每次给出要争吵的猴子a和b，用并查集判断如果他们是朋友输出-1如果不是，找出a，b在的堆的根A，B，分别合并A，B的左右孩子，再合并一下。之后把A，B的数据更改一下：权值除以2，左右孩子设为0，再插入到堆中即可。最后输出堆顶。*/ #include <iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N = 100005;int m,n;int set[N];struct node{    int l,r,dis,key;}tree[N];int find(int x) {return set[x] == x ? x : set[x] = find(set[x]);}int merge(int a,int b){    if(!a)        return b;    if(!b)        return a;    if(tree[a].key < tree[b].key)//大堆        swap(a,b);    tree[a].r = merge(tree[a].r,b);    set[tree[a].r] = a;//并查    if(tree[tree[a].l].dis < tree[tree[a].r].dis)        swap(tree[a].l,tree[a].r);    if(tree[a].r)        tree[a].dis = tree[tree[a].r].dis + 1;    else        tree[a].dis = 0;    return a;}int pop(int a){    int l = tree[a].l;    int r = tree[a].r;    set[l] = l;//因为要暂时删掉根，所以左右子树先作为根    set[r] = r;    tree[a].l = tree[a].r = tree[a].dis = 0;    return merge(l,r);}int nextint(){    char c;    int ret = 0;    while((c = getchar()) > ‘9‘ || c < ‘0‘)        ;    ret = c - ‘0‘;    while((c = getchar()) >= ‘0‘ && c <= ‘9‘)        ret = ret * 10 + c - ‘0‘;    return ret;}void print(int a){    if(!a)        return;    print(a/10);    putchar(a%10 + ‘0‘);}int main(){    int a,b,i;    while(~scanf("%d",&n))    {        for(i = 1;i <= n;i ++)        {;            tree[i].key = nextint();            set[i] = i;            tree[i].l = tree[i].r = tree[i].dis = 0;        }        m = nextint();        while(m --)        {            a = nextint();            b = nextint();            int ra = find(a);            int rb = find(b);            if(ra == rb)                printf("-1\n");            else            {                int rra = pop(ra);//ra左右子树合并                tree[ra].key /= 2;                ra = merge(rra,ra);//重新插入ra 找到合适的位置                int rrb = pop(rb);                tree[rb].key /= 2;                rb = merge(rrb,rb);                print(tree[merge(ra,rb)].key);                putchar(10);            }        }    }    return 0;}