#include <iostream>
#include <string>
#include <unordered_map>
#include <set>
#include <vector>

using namespace std;

#include <cassert>

/** Begin fast allocation */
const int MAX_MEM = 2e8;
int mpos = 0;
char mem[MAX_MEM];
inline void * operator new ( size_t n ) {
    assert((mpos += n) <= MAX_MEM);
    return (void *)(mem + mpos - n);
}
inline void operator delete ( void * ) noexcept { } // must have!
/** End fast allocation */

#include "optimization.h"

const int MAXN = 300001;
int id, y;

int vect[MAXN];
unordered_map<int, set<int>> table(MAXN); // по значению индекс
set<pair<int, int>> setp; // количество, индекс

void change(int id, int y) {
    setp.erase({(int)table[vect[id]].size(), *table[vect[id]].begin()});
    table[vect[id]].erase(id); // убрать i из элементов в сете для данного значения
    if ((int)table[vect[id]].size() > 0)
        setp.insert({(int)table[vect[id]].size(), *table[vect[id]].begin()});

    setp.erase({(int)table[y].size(), *table[y].begin()});
    table[y].insert(id);
    setp.insert({(int)table[y].size(), *table[y].begin()});

    vect[id] = y; // изменить значение в векторе

    return;
}

int get() {
    return (*setp.begin()).second; // как правильно это написать?
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q, ind;
    n = readInt();
    int a;
    for (int i = 0; i < n; i++) {
        a = readInt();
        vect[i] = a;
        table[a].insert(i);
        // надо снова как в change пройтись по всему сету? мб вообще можно как-то вызвать change...
    }
    for (auto it : table) {
        setp.insert({(int)it.second.size(), *it.second.begin()});
    }
    q = readInt();
    string s;
    char c;
    int id, y;
    for (int i = 0; i < q; i++) {
        c = readChar();
        if (c == '?') {
            writeInt(get(), '\n');
        } else {
            id = readInt();
            y = readInt();
            change(id, y);
        }
    }
    return 0;