1558: 猴王

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

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

分为两部分。

第一部分，第一行有一个整数n(n<=100,000),代表猴子总数。

    接下来的n行,每行一个数表示每只猴子的强壮值(<=32768)。

第二部分，第一行有一个整数m(m<=100,000),表示有m次冲突会发生。

接下来的m行,每行包含两个数x和y,代表第x个猴子和第y个猴子之间发

生冲突。

输出每次决斗后在它们所有朋友中的最大强壮值。

数据保证所有猴子决斗前彼此不认识。

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

8
5
5
10