大体思路就是先删除两个堆顶，然后把新节点合并，再跟原来合并过的两个根一顿合并。

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n, Q, w[N], l[N], r[N], idx = 0, dist[N], fa[N];

inline int max(int x, int y)
{
	return x > y ? x : y;
}

inline int get(int val)
{
	w[++ idx] = val, dist[idx] = 1, fa[idx] = idx;
	return idx;
}
 
inline int find(int x)
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

inline bool cmp(int x, int y)
{
	return w[x] > w[y];
}
 
 inline int merge(int x, int y)
 {
 	if(x == 0 or y == 0)	
 		return x + y;
 	if(cmp(y, x))
 		swap(x, y);
	r[x] = merge(r[x], y);
 	if(dist[r[x]] > dist[l[x]])
 		swap(l[x], r[x]);
 	dist[x] = dist[r[x]] + 1;
 	return x;
 }

inline int update(int x, int y) // 具体执行合并操作，包括更改父子关系
{
	if(cmp(y, x))
		swap(x, y);
	fa[y] = x;
	return merge(x, y);
}

inline int del(int x) // 将x删除 合并其左右子树 返回根节点
{
	if(cmp(r[x], l[x]))
		swap(l[x], r[x]);
	fa[x] = l[x], fa[l[x]] = l[x]; 
	return merge(l[x], r[x]);
}
 
inline int query(int x, int y)
{
	int A = w[x] >> 1, B = w[y] >> 1, root = update(get(A), get(B));
	int rootA = del(x), rootB = del(y);
	if(rootA == -1 and rootB == -1)
		return w[root];
	else if(rootA == -1 or rootB == -1)
		return w[root = update(root, max(rootA, rootB))];
	else
		return w[root = update(root, update(rootA, rootB))];
}
 
int main()
{
	while(~scanf("%d", &n))
	{
		memset(fa, 0, sizeof fa), idx = 0;
		memset(l, 0, sizeof l), memset(r, 0, sizeof r);
		for(int i(1), val; i <= n; ++ i)
			scanf("%d", &val), get(val);
		scanf("%d", &Q);
		while(Q -- )
		{
			int x, y;
			scanf("%d %d", &x, &y);
			x = find(x), y = find(y);
			// cerr << x << " " << y << '\n';
			// cerr << w[x] << " " << w[y] << '\n' << '\n';
			if(x == y)
				puts("-1");
			else
				printf("%d\n", query(x, y));
		}
	}
	return 0;
}