题目描述

曾经在一个森林中居住着 $N$ 只好斗的猴子。在最初他们我行我素，互不认识。但是猴子们不能避免争吵，且两只猴子只会在不认识对方时发生争吵，当争吵发生时，双方会邀请它们各自最强壮的朋友并发起决斗（决斗的为各自最强壮的朋友）。当然，在决斗之后两只猴子和他们各自的伙伴都认识对方了（成为朋友），虽然他们曾经有过冲突，但是他们之间绝不会再发生争吵了。

假设每只猴子有一个强壮值，强壮值将在一场决斗后减少为原先的一半（例如 $10$ 会减少到 $5$，而 $5$ 会减少到 $2$，即向下取整）。

我们也假设每只猴子都认识它自己（是自己的朋友）。即当他是他朋友中最强壮的，他自己就会去决斗。

输入格式

有多组数据，每一组数据有两部分。

第一部分：第一行包含一个整数 $N$ 表示猴子的数量。后为 $N$ 行，每行一个数字为第 $i$ 只猴子的强壮值 $s_{i}$。

第二部分：第一行包含一个整数 $M$ 表示发生了 $M$ 次冲突。后为 $M$ 行，每行两个整数 $x$ 和 $y$，表示第 $x$ 只猴子和第 $y$ 只猴子之间发生了冲突。

输出格式

对于每次冲突，如果两只猴子认识对方，输出 -1，否则输出决斗后他们朋友中最强壮的猴子的强壮值。

样例 #1

样例输入 #1

5
20
16
10
10
4
5
2 3
3 4
3 5
4 5
1 5

样例输出 #1

8
5
5
-1
10

提示

对于 $100\%$ 数据，$N,M\leq 100000$，$s_{i}\leq 32768$

题目可能有多组数据