Untitled

 avatar
domovonok
c_cpp
a year ago
2.5 kB
5
Indexable
#include <bits/stdc++.h>
using namespace std;


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

/*
ifstream fin("input.txt");
ofstream fout("output.txt");
#define cin fin
#define cout fout
*/

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define lwb lower_bound
#define upb upper_bound
#define all(x) (x).begin(), (x).end()
#define int long long
//#define double long double
#define ll long long
#define X real()
#define Y imag()
const int INF = 1e18, N = 1000000, P = 998244353, K = 26, C = 300;
const double EPS = 1e-7;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& it : a)
        cin >> it;
    vector<vector<pair<int, int>>> d(n / C + 1);
    for (int i = 0; i < n; i++) {
        d[i / C].eb(a[i], i);
    }
    for (auto& it : d)
        sort(all(it));
    int q;
    cin >> q;
    while (q--) {
        int type, i;
        cin >> type >> i;
        i--;
        if (type == 1) {
            int val = a[i], ans = a[n - 1];
            int j = i / C;
            for (auto [x, y] : d[j]) {
                if (x > val && x < ans && y > i)
                    ans = x;
            }
            j++;
            while (j <= n / C) {
                auto t = upb(all(d[j]), make_pair(val, INF));
                if (t != d[j].end())
                    ans = min(ans, t->fi);
                j++;
            }
            cout << ans << '\n';
        }
        else {
            int j = i / C;
            a[i] = -a[i];
            for (auto& [x, y] : d[j]) {
                if (y == i) {
                    x = -x;
                    break;
                }
            }
            sort(all(d[j]));
        }
    }
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


signed main() {
    //cout << fixed << setprecision(15);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
}