#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <vector>
#include <unordered_map>
#include <numeric>
#include <random>
#include <set>

//#define FAST_ALLOCATOR_MEMORY 1e8
#include "optimization.h"

using namespace std;

struct S {
    int val, cnt, index;

    S() {}
    S(int _val, int _cnt, int _index) : val(_val), cnt(_cnt), index(_index) {}

    bool operator < (const S& s) const {
        if (cnt == s.cnt)
            return index < s.index;
        return cnt < s.cnt;
    }
};

const int MAXN = 3e5 + 7;

int ms[MAXN];

signed main(void) {
    #ifdef LOCAL
        freopen("a.in", "r", stdin);
        freopen("a.out", "w", stdout);
    #endif
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int x, n = readInt();
    unordered_map<int, set<int>> mp(5 * n);
    set<S> s;
    for (int i = 0; i < n; ++i) {
        x = readInt();
        mp[x].insert(i);
        ms[i] = x;
    }
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        s.insert({it->first, (int)it->second.size(), *it->second.begin()});
    }
    int q = readInt(), y;
    char command;
    set<S>::iterator it;
    unordered_map<int, set<int>>::iterator mit;
    while (q --> 0) {
        command = readChar();
        if (command == '?') {
            it = s.begin();
            writeInt(it->index, '\n');
        } else {
            x = readInt(), y = readInt();
            mit = mp.find(ms[x]);
            s.erase({ms[x], (int)mit->second.size(), *mit->second.begin()});
            mit->second.erase(x);
            if ((int)mit->second.size() == 0)
                mp.erase(ms[x]);
            else
                s.insert({ms[x], (int)mit->second.size(), *mit->second.begin()});
            mit = mp.find(y);
            if (mit != mp.end())
                s.erase({y, (int)mit->second.size(), *mit->second.begin()});
            else
                mp.insert({y, {}}), mit = mp.find(y);
            mit->second.insert(x);
            ms[x] = y;
            s.insert({y, (int)mit->second.size(), *mit->second.begin()});
        }
    }
}