#2548. 猴王

猴王

Description

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

Format

Input

输入包含几个测试用例,每个测试用例都由两部分组成。第11部分的第11行包含一个整数NN105N(N≤10^5),表示猴子的数量;接下来的NN行,每行都有一个数字,表示第ii个猴子的强壮值ViVi32768Vi(Vi≤32768)。第22部分的第11行包含一个整数MM105M(M≤10^5),表示发生了MM次冲突;接下来的M行,每行都包含两个整数xyx、y,表示第xx个猴子和第yy个猴子之间存在冲突。

Output

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

Samples

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

来源

HDU1512