记录编号	540430	评测结果	AAAAAAAAAA
题目名称	[HDU 1512] 爱争吵的猴子	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.221 s
提交时间	2019-08-23 20:30:21	内存使用	22.05 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
priority_queue<int> que[N];
int a[N],fa[N],n,sz[N];
#define I inline
int find(int x)
{
	if (fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
I int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
/*int solve(int x,int y)
{
	int sx=sz[x],sy=sz[y],ans;
	if (sx>sy) swap(sx,sy);
	fa[x]=y;
	int p=que[x].top(),q=que[y].top();
	que[x].pop();que[y].pop();
	while (!que[x].empty())
	{
		int p=que[x].top();que[x].pop();
		que[y].push(p);
	}
	que[y].push(p/2);que[y].push(q/2);
	sz[y]=sz[x]+sz[y];
	return que[y].top();
}*/
void solve(int x,int y)
{
	int p=find(x),q=find(y);
	if (p==q) {printf("%d\n",-1);return;}
	else
	{
		if (sz[p]>sz[q]) swap(p,q);
		int x=que[p].top(),y=que[q].top();
		que[p].pop();que[q].pop();
		fa[p]=q;
		while (!que[p].empty())
		{
			int x=que[p].top();que[p].pop();
			que[q].push(x);
		}
		que[q].push(x/2);que[q].push(y/2);
		printf("%d\n",que[q].top());
		sz[q]=sz[q]+sz[p];
	}
}
int main()
{
	freopen("monkeyk.in","r",stdin);
	freopen("monkeyk.out","w",stdout);
	n=read();
	for (int i=1;i<=n;i++) a[i]=read(),fa[i]=i,que[fa[i]].push(a[i]),sz[i]=1;
	int Q=read();
	while (Q--)
	{
		int x=read(),y=read();
		solve(x,y);
	}
	return 0;
}