Description

在森林里住着$N$只好斗的猴子。开始时，猴子们彼此不认识，难免吵架，吵架只发生在互不认识的两只猴子之间。吵架发生时，两只猴子都会邀请它们中最强壮的朋友来决斗。决斗过后，两只猴子和它们的所有朋友都认识对方，吵架不再发生。假设每只猴子都有一个强壮值，决斗后，强壮值会减少到原来的一半（即$10$将减少到$5$，$5$将减少到$2$）；且每只猴子都认识自己，如果它是所有朋友中最强壮的，那么它自己也会去决斗。确定决斗后它们所有朋友的最大强壮值。

Format

Input

输入包含几个测试用例，每个测试用例都由两部分组成。第$1$部分的第$1$行包含一个整数$N（N≤105）$，表示猴子的数量；接下来的$N$行，每行都有一个数字，表示第$i$个猴子的强壮值$Vi（Vi≤32768）$。第$2$部分的第$1$行包含一个整数$M（M≤105）$，表示发生了$M$次冲突；接下来的M行，每行都包含两个整数$x、y$，表示第$x$个猴子和第$y$个猴子之间存在冲突。

Output

对每一次冲突，若两只猴子互相认识，则都输出$-1$，否则输出决斗后它们所有朋友的最大强壮值。

Samples

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

8
5
5
-1
10