题目

科学家用 AI 模拟生命体的族群分类情况，假设有 $n$ 个新生的生命体，每个生命体都有一个生命值，两个生命体相遇时会发生从斗争到认识到合并到同一族群的过程，在不同族群里面的生命体，如果相遇时，会找到本族群最强者进行两两对决，每次斗争都会让参与者的生命值减半，例如原来是生命值 10，进行斗争后变成 5，原来是 5，进行斗争后变成 2，如果生命值是 1，斗争后还维持为 1。斗争后两个族群就合并在一起了，如果两个生命体来自于同一个个族群，则它们不会发生斗争问题。请编写程序，求出每一个对决序列，两个相遇的生命体进行对决后，组成的新的族群的最强者的生命值，如果该对决序列的两个生命体属于同一族群则输出 -1。

样例

input:

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

output:

8
5
5
-1
10