记录编号	337605	评测结果	AAAAAAAAAA
题目名称	[HDU 1512] 爱争吵的猴子	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.510 s
提交时间	2016-11-04 17:56:18	内存使用	2.00 MiB

//QaQ
#include <cstdio>
#include <cstdarg>
#include <cstring>
#include <string>
#include <iostream>
#include <list>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
#define BETTER_CODE __attribute__((optimize("O3")))
#define INF = 0x7fffffff;

BETTER_CODE
inline int fast_read()
{
    char c;
    int r;
    while(c = getchar())
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return r;
}
struct node
{
    int l, r, v, dist, f;
}heap[100003];
BETTER_CODE
int merge(int a, int b)
{
    if(a == 0)return b;
    if(b == 0)return a;
    if(heap[a].v < heap[b].v)swap(a, b);
    heap[a].r = merge(heap[a].r, b);
    heap[heap[a].r].f = a;
    
    if(heap[heap[a].l].dist < heap[heap[a].r].dist)
        swap(heap[a].l, heap[a].r);
    if(heap[a].r == 0)heap[a].dist = 0;
    else heap[a].dist = heap[heap[a].r].dist+1;
    return a;
}
BETTER_CODE
int pop(int x)
{
    int l = heap[x].l;
    int r = heap[x].r;
    heap[l].f = l;
    heap[r].f = r;
    heap[x].l = heap[x].r = heap[x].dist = 0;
    return merge(l, r);
}
BETTER_CODE
int find(int x){return heap[x].f == x? x:find(heap[x].f);}

int main()
{
    freopen("monkeyk.in", "r", stdin);
    freopen("monkeyk.out", "w", stdout);
    int n = fast_read();
    for(int i = 1; i <= n; i++)
    {
        heap[i].v = fast_read();
        heap[i].f = i;
    }
    int m = fast_read();
    int x, y;
    while(m--)
    {
        x = fast_read();
        y = fast_read();
        int fx = find(x);
        int fy = find(y);
        if(fx == fy)printf("-1\n");
        else
        {
            heap[fx].v >>= 1;
            int u = pop(fx);
            u = merge(u, fx);
            
            heap[fy].v >>= 1;
            int v = pop(fy);
            v = merge(v, fy);
            printf("%d\n", heap[merge(u, v)].v);
        }
    }
    return 0;
}