猴王2

Description:

很久很久以前,在一个广阔的森林里,住着n只好斗的猴子。起初,它们各干各的,互相之间也不了解。但是这并不能避免猴子们之间的争吵,当然,这只存在于两个陌生猴子之间。当两只猴子争论时,它们都会请自己最强壮的朋友来代表自己进行决斗。显然,决斗之后,这两只猴子以及它们的朋友就互相了解了,这些猴子之间将再也不会发生争论了,即使它们曾经发生过冲突。

假设每一只猴子都有一个强壮值,每次决斗后都会减少一半(比如10会变成5,5会变成2)。并且我们假设每只猴子都很了解自己。就是说,当它属于所有朋友中最强壮的一个时,它自己会站出来,走向决斗场。

 

 

Input:

分为两部分。
第一部分，第一行有一个整数n(n<=100,000),代表猴子总数。
    接下来的n行,每行一个数表示每只猴子的强壮值(<=32768)。
第二部分，第一行有一个整数m(m<=100,000),表示有m次冲突会发生。
接下来的m行,每行包含两个数x和y,代表第x个猴子和第y个猴子之间发
生冲突。

Output:

输出每次决斗后在它们所有朋友中的最大强壮值。如果它们本身就是朋友则输出-1。

Sample Input:

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

Sample Output:

8
5
5
-1
10

Note:

 

本题由旧版NOJ导入，来源：JSOI2010