Untitled

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

using ll = long long;
using ull = unsigned long long;
using db = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<db, db>;
using tiii = tuple<int, int, int>;
using str = string;

#define vt vector
#define pb push_back
#define eb emplace_back
#define ins insert
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second

constexpr int maxA = 1e6;

struct segtree {

    int size;
    vt<int> tree;

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size - 1, INT_MIN);
    }

    void set(int i, int v, int x, int lx, int rx) {
        if (rx - lx == 1) {
            tree[x] = v;
        } else {
            int m = (lx + rx) / 2;
            if (i < m) {
                set(i, v, x * 2 + 1, lx, m);
            } else {
                set(i, v, x * 2 + 2, m, rx);
            }
            tree[x] = max(tree[x * 2 + 1], tree[x * 2 + 2]);
        }
    }

    void set(int i, int v) {
        set(i, v, 0, 0, size);
    }

    int calc(int l, int r, int v, int x, int lx, int rx) {
        if (rx - lx == 1) {
            return tree[x];
        } else {
            int m = (lx + rx) / 2;
            if (tree[x * 2 + 1] > v && m > l) {
                int t = calc(l, r, v, x * 2 + 1, lx, m);
                if (t == INT_MIN && tree[x * 2 + 2] > v) {
                    return calc(l, r, v, x * 2 + 2, m, rx);
                }
                return t;
            } else if (tree[x * 2 + 2] > v) {
                return calc(l, r, v, x * 2 + 2, m, rx);
            }
            return INT_MIN;
        }
    }

    int calc(int l, int v) {
        return calc(l, size, v, 0, 0, size);
    }

};

void solve() {
    segtree tr;
    tr.init(2 * maxA + 1);
    int n;
    cin >> n;
    vt<int> a(n);
    map<int, set<int>> cnts;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cnts[a[i]].ins(i);
        tr.set(a[i] + maxA, i);
    }
    int q;
    cin >> q;
    while (q--) {
        int t, i;
        cin >> t >> i;
        i--;
        if (t == 1) {
            int c = tr.calc(a[i] + 1 + maxA, i);
            cout << a[c] << '\n';
        } else {
            cnts[a[i]].erase(i);
            cnts[-a[i]].ins(i);
            tr.set(a[i] + maxA, (cnts[a[i]].empty() ? INT_MIN : *--cnts[a[i]].end()));
            tr.set(-a[i] + maxA, *--cnts[-a[i]].end());
            a[i] = -a[i];
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        solve();
    }
    return 0;
}