fila beauty

#include <bits/stdc++.h>

using namespace std;

int raiz = 1200;

struct bucket{
    int maior; //change
    vector<int> valores;
};

vector<bucket> arr(1);

void print(){
    for(int i = 0; i < arr.size(); i++){
        cout << "bucket #" << (i+1) <<" (" << arr[i].maior << ") -> ";
        for(int j = 0; j < arr[i].valores.size(); j++){
            cout << arr[i].valores[j] << " \n"[j == arr[i].valores.size()-1];
        }
    }
}

void change_max(bucket &actual){
    actual.maior = 0;
    for(int i = 0; i < actual.valores.size(); i++){
        actual.maior = max(actual.maior, actual.valores[i]);
    }
}

void split(bucket &actual, int idx){
    bucket novo;
    novo.valores.assign(actual.valores.begin()+ raiz, actual.valores.end());
    actual.valores.resize(raiz);
    change_max(novo);
    change_max(actual);
    arr.insert(arr.begin()+idx + 1, novo);
}

void insert(int val, int idx, int bucket_idx = 0){
    for(int i = bucket_idx; i < arr.size(); i++){
        bucket &actual = arr[i];
        if(idx <= actual.valores.size()){
            actual.valores.insert(actual.valores.begin() + idx, val);
            change_max(actual);
            if(actual.valores.size() >= 2*raiz) split(actual, i);
            //print();
            return;
        }
        idx -= actual.valores.size();
    }
}

pair<int, int> at(int idx){
    for(int i = 0; i < arr.size(); i++){
        bucket &actual = arr[i];
        //cout << idx << " " << actual.valores.size() << endl;
        if(idx < actual.valores.size()){
            return make_pair(i, idx);
        }

        idx -= actual.valores.size();
    }
}
void erase(int idx){
    pair<int,int> pos = at(idx);
    bucket &actual = arr[pos.first];

    actual.valores.erase(actual.valores.begin()+pos.second);
    if(actual.valores.size() == 0) arr.erase(arr.begin()+pos.first);
    else change_max(actual);
}

int query(int idx, int val){
    pair<int, int> pos = at(idx);

    //cout << "fase 1\n";
    while(pos.second >= 0){
        if(arr[pos.first].valores[pos.second] > val) return idx;
        pos.second--;
        idx--;
    }

    //cout << "fase 2\n";
    pos.first--;
    while(pos.first >= 0){
        if(arr[pos.first].maior > val) break;
        idx -= arr[pos.first].valores.size();
        pos.first--;
    }

    //cout << "fase 3\n";
    if(idx > 0) pos = at(idx);
    while(pos.second >= 0){
        if(arr[pos.first].valores[pos.second] > val) return idx;
        pos.second--;
        idx--;
    }

    return -1;
}
int main(){
    int n; scanf("%d", &n);
    for(int i = 0; i < n; i++){
        int val; scanf("%d", &val);
        insert(val, i);
    }
    int q; scanf("%d", &q);
    while(q--){
        int type, pos, val; scanf("%d %d %d", &type, &pos, &val);
        if(type == 0){
            insert(val, pos);
        }else{
            pos--;
            pair<int, int> idx = at(pos);
            //cout << idx.first << " " << idx.second << endl;
            printf("%d\n", query(pos-1, arr[idx.first].valores[idx.second] + val) + 1);
        }
    }
    return 0;
}