#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define popcount __builtin_popcount
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q; cin >> n;
int A[n], vals[n+1];
for (int i = 0; i < n; i++) {
cin >> A[i];
vals[i] = A[i];
}
vals[n] = 1e9+1;
sort(vals, vals + n+1);
vector<int> pos[n+1];
for (int i = 0; i < n; i++) {
pos[ lower_bound(vals, vals+n+1, A[i]) - vals ].push_back(i);
}
cin >> q;
vector<int> L, R, K, P;
int cnt = 0;
for (int i = 0; i < q; i++) {
int t, l, r; cin >> t;
if (t == 1) cnt++;
else {
cin >> l >> r;
l--;
L.push_back(0);
R.push_back(n);
K.push_back(cnt);
P.push_back(l);
}
}
vector<int> queries[n+1];
q = L.size();
if (q == 0) return 0;
auto iterate = [&]() {
for (int i = 0; i < q; i++) {
queries[ (L[i] + R[i])/2 ].push_back(i);
}
bool isless[n]{};
ordered_set<int> s;
for (int x = 0; x <= n; x++) {
for (int i : queries[x]) {
int case1 = P[i] + K[i] < n ? isless[P[i] + K[i]] : 0;
int case2 = P[i] < s.size() ? *s.find_by_order(P[i]) - K[i] <= P[i] : 0;
// cout << i << " " << K[i] << " " << vals[x] << " " << case1 << case2 << "\n";
if (case1 | case2) {
R[i] = x;
} else {
L[i] = x;
}
}
queries[x].clear();
for (int i : pos[x]) {
isless[i] = true;
s.insert(i);
}
}
};
while (L[0] + 1 < R[0]) iterate();
for (int i = 0; i < q; i++)
cout << vals[L[i]] << "\n";
}
