seg sqrt

#include <bits/stdc++.h>
#define MAX 10000007

using namespace std;

int raiz, n;
vector<int> block;
vector<vector<int> > arr;
int val[MAX];

void print(){
    for(int i = 0; i < arr.size(); i++){
        cout << "Raiz " << (i+1) << " = ";
        for(int j = 0; j < arr[i].size(); j++){
            cout << arr[i][j] << " \n"[j == arr[i].size()-1];
        }
    }
    cout << "\nblocks = ";
    for(int i = 0; i < block.size(); i++) cout << block[i] << " \n"[i == block.size()-1];
    cout << "new raiz is " << raiz << endl;
}

int bucket(int idx){
    int ans = 0, cnt = 0;
    for(int i = 0; i <= raiz; i++) {
        if(arr[i].size()+cnt >= idx) return ans;
        ans++;
        cnt += arr[i].size();
    }
    return ans;
}

int index(int idx){
    int cnt = 0;
    for(int i = 0; i <= raiz; i++) {
        if(arr[i].size()+cnt >= idx) return idx-cnt;
        cnt += arr[i].size();
    }
    return 0;
}
void build(){
    raiz = (int) sqrt(n) + 1;
    arr.assign(raiz+1, vector<int> ());
    block.assign(raiz+1, 0);
    int actual = -1;
    for(int i = 0; i < n; i++){
        //cout << i << " " << raiz << " " << (i%raiz) << endl;
        if(i%raiz == 0) actual++;
        arr[actual].push_back(val[i]);
        block[actual] = max(block[actual], val[i]);
    }
}

void resize(int idx){
    vector<int> old = arr[idx];
    arr.erase(arr.begin()+idx);
    block[idx] = 0;
    block.insert(block.begin()+idx, 0);
    vector<int> novo;
    for(int i = 0; i < old.size(); i++){
        if(novo.size() == raiz) {
            arr.insert(arr.begin()+idx, novo);
            idx++;
            novo.clear();
        }
        novo.push_back(old[i]);
        block[idx] = max(block[idx], old[i]);
    }
    if(novo.size()){
        arr.insert(arr.begin()+idx, novo);
        novo.clear();
    }
}

void insert(int val, int idx){
    int actual = bucket(idx);
    //cout << actual << endl;

    idx = index(idx);
    //cout << idx << endl;
    arr[actual].insert(arr[actual].begin() + idx, val);
    //cout << "inseriu\n";
    block[actual] = max(block[actual], val);
    raiz = sqrt(++n) + 1;
    //print();
    if(arr[actual].size() >=  2*raiz) resize(actual);
}

int find(int idx, int val){
    int block_idx = bucket(idx);

    //cout << block_idx << " " << val << endl;
    int borda = idx-index(idx);
    //cout << idx << " " << borda << endl;
    idx--;
    while(idx >= borda){
        //cout << "initial block\n";
        if(arr[block_idx][idx-borda] > val) return idx+1;
        idx--;
    }

    //cout << idx << " " << borda << endl;
    while(idx >= 0){
        //cout << "find a new block\n";
        block_idx--;
        if(block[block_idx] > val) break;
        idx -= arr[block_idx].size();
    }

    borda = idx-index(idx);
    while(idx >= borda){
        //cout << "final block\n";
        if(arr[block_idx][idx-borda] > val) return idx+1;
        idx--;
    }
    return 0;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> val[i];
    build();
    //print();
    int q; cin >> q;
    while(q--){
        int type, x, y;  cin >> type >> x >> y;
        if(type == 0){
            insert(y, x);
            //print();
        }else{
            int z = arr[bucket(x)][index(x)-1];
            //cout << "z = " << z << endl;
            cout << find(x, y+z) << endl;
        }
    }
    return 0;
}