RT

#include <bits/stdc++.h>
using namespace std;

struct BinNode {
    int key;
    int deg;
    BinNode* child;
    BinNode* parent;
    BinNode* next;
    BinNode(int value)
        : key(value)
        , deg(0)
        , child(NULL)
        , parent(NULL)
        , next(NULL) { }
};

typedef BinNode bn;
typedef BinNode* bt;

struct BinHeap { // 二项堆结构，它包括了二项堆的根节点mRoot以及二项堆的基本操作的定义。
public:
    BinNode* mRoot; // 根结点

    BinHeap(int x) {
        mRoot = new BinNode(x);
    }
    void insert(int key);
    void update(int oldkey, int newkey);
    void remove(int key);
    void extractMinimum();
    void combine(BinHeap* other);
    int minimum();
    bool contains(int key);
    void print();

private:
    void link(BinNode* child, BinNode* root);
    BinNode* merge(BinNode* h1, BinNode* h2);
    BinNode* combine(BinNode* h1, BinNode* h2);
    BinNode* reverse(BinNode* root);
    BinNode* extractMinimum(BinNode* root);
    BinNode* remove(BinNode* root, int key);
    BinNode* search(BinNode* root, int key);

    void increaseKey(BinNode* node, int key);
    void decreaseKey(BinNode* node, int key);
    void updateKey(BinNode* node, int key);

    void minimum(BinNode* root, BinNode*& prev_y, BinNode*& y);
    void print(BinNode* node, BinNode* prev, int direction);
};

bt mRoot;

bt BinHeap::merge(bt h1, bt h2) {
    bt root = nullptr;
    bt* pos = &root;
    while (h1 and h2) {
        if (h1->deg < h2->deg) {
            *pos = h1;
            h1 = h1->next;
        } else {
            *pos = h2;
            h2 = h2->next;
        }
        pos = &(*pos)->next;
    }
    if (h1)
        *pos = h1;
    else
        *pos = h2;
    return root;
}

void BinHeap::link(bt child, bt root) {
    child->parent = root;
    child->next = root->child;
    root->child = child;
    root->deg++;
}

bt BinHeap::search(bt root, int key) {
    bt child;
    bt parent = root;
    parent = root;
    while (parent != nullptr) {
        if (parent->key == key)
            return parent;
        if ((child = search(parent->child, key)) != nullptr)
            return child;
        parent = parent->next;
    }
    return nullptr;
}

bt BinHeap::combine(bt h1, bt h2) {
    bt root;
    bt prev_x, x, next_x;
    root = merge(h1, h2);
    if (root == nullptr)
        return nullptr;
    prev_x = nullptr;
    x = root;
    next_x = x->next;
    while (next_x != nullptr) {
        if (x->deg != next_x->deg
            or next_x->next != nullptr
                and next_x->deg == next_x->next->deg) {
            prev_x = x;
            x = next_x;
        } else if (x->key <= next_x->key) {
            x->next = next_x->next;
            link(next_x, x);
        } else {
            if (prev_x == nullptr)
                root = next_x;
            else
                prev_x->next = next_x;
            link(x, next_x);
            x = next_x;
        }
        next_x = x->next;
    }
    return root;
}

void BinHeap::combine(BinHeap* other) {
    if (other != NULL && other->mRoot != NULL)
        mRoot = combine(mRoot, other->mRoot);
}

bool BinHeap::contains(int key) {
    return search(mRoot, key) != nullptr;
}

void BinHeap::insert(int key) {
    bt node;
    node = new BinNode(key);
    if (node == nullptr)
        return;
    mRoot = combine(mRoot, node);
}

bt BinHeap::reverse(bt root) {
    bt next;
    bt tail = nullptr;
    if (!root)
        return root;
    root->parent = nullptr;
    while (root->next) {
        next = root->next;
        root->next = tail;
        tail = root;
        root = next;
        root->parent = nullptr;
    }
    root->next = tail;
    return root;
}

bt BinHeap::remove(bt root, int key) {
    bt node;
    bt parent, prev, pos;

    if (root == nullptr)
        return root;

    if ((node = search(root, key)) == nullptr)
        return root;

    parent = node->parent;
    while (parent != nullptr) {
        swap(node->key, parent->key);
        node = parent;
        parent = node->parent;
    }

    prev = nullptr;
    pos = root;
    while (pos != node) {
        prev = pos;
        pos = pos->next;
    }

    if (prev)
        prev->next = node->next;
    else
        root = node->next;

    root = combine(root, reverse(node->child));
    delete node;
    return root;
}

void BinHeap::remove(int key) {
    mRoot = remove(mRoot, key);
}

void BinHeap::decreaseKey(bt node, int key) {
    if (key >= node->key) {
        return;
    }
    node->key = key;

    bt child, parent;
    child = node;
    parent = node->parent;
    while (parent != nullptr and child->key < parent->key) {
        swap(parent->key, child->key);
        child = parent;
        parent = child->parent;
    }
}

void BinHeap::increaseKey(bt node, int key) {
    if (key <= node->key)
        return;

    node->key = key;

    bt cur, child, least;
    cur = node;
    child = cur->child;
    while (child != nullptr) {
        if (cur->key > child->key) {
            least = child;
            while (child->next != nullptr) {
                if (least->key > child->next->key)
                    least = child->next;
                child = child->next;
            }
            swap(least->key, cur->key);
            cur = least;
            child = cur->child;
        } else {
            child = child->next;
        }
    }
}

void BinHeap::updateKey(bt node, int key) {
    if (node == nullptr)
        return;
    if (key < node->key)
        decreaseKey(node, key);
    else if (key > node->key)
        increaseKey(node, key);
}

void BinHeap::update(int oldkey, int newkey) {
    updateKey(mRoot, newkey);
}

void BinHeap::print(bt node, bt prev, int direction) {
    while (node != nullptr) {
        if (direction == 1)
            cout << "\t" << setw(2) << node->key << "(" << node->deg << ") is"
                 << setw(2) << prev->key << "'s child" << endl;
        else
            cout << "\t" << setw(2) << node->key << "(" << node->deg << ") is"
                 << setw(2) << prev->key << "'s next" << endl;
        if (node->child != nullptr)
            print(node->child, node, 1);

        prev = node;
        node = node->next;
        direction = 2;
    }
}

void BinHeap::print() {
    bt p;
    if (mRoot == nullptr)
        return;

    cout << "== 二项堆( ";
    p = mRoot;
    while (p != nullptr) {
        cout << "B" << p->deg << " ";
        p = p->next;
    }
    cout << ")的详细信息：" << endl;

    int i = 0;
    p = mRoot;
    while (p != nullptr) {
        i++;
        cout << i << ". 二项树B" << p->deg << ":" << endl;
        cout << "\t" << setw(2) << p->key << "(" << p->deg << ") is root" << endl;
        print(p->child, p, 1);
        p = p->next;
    }
    cout << endl;
}

int n, m;

vector<BinHeap> v;

struct Union {
    int n; // node sums
    vector<int> p; // parent

    Union(int _n) {
        n = _n;
        p = vector<int>(n + 2);
        for (int i = 1; i <= n; i++)
            p[i] = i;
    }

    int get(int x) {
        if (x == p[x])
            return x;
        return p[x] = get(p[x]);
    }

    void merge(int x, int y) {
        x = get(x);
        y = get(y);
        p[x] = y;
    }

    bool check(int x, int y) {
        return get(x) == get(y);
    }
};

void work() {
    v.clear();
    v.push_back(BinHeap(0));
    Union u(n);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        v.push_back(BinHeap(-x));
    }

    cin >> m;

    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        x = u.get(x);
        y = u.get(y);
        if (x == y) {
            cout << -1 << endl;
            continue;
        }
        u.merge(x, y);
        v[y].update(v[y].mRoot->key, -(-v[y].mRoot->key / 2));
        v[x].update(v[x].mRoot->key, v[x].mRoot->key / 2);
        v[y].combine(&v[x]);
        cout << -v[y].mRoot->key << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    while (cin >> n)
        work();

    return 0;
}