fila desgraçada

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

using namespace std;

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

int siz(int idx){
    int ans = 0;
    int actual = idx/raiz;
    for(int i = 0; i < actual; i++) ans += arr[i].size();

    return ans;
}

void build(){
    raiz = (int) sqrt(n);
    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];
    }
    if(novo.size()){
        arr.insert(arr.begin()+idx, novo);
        novo.clear();
    }
}

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

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

int find(int idx, int val){
    int block_idx = idx/raiz;

    cout << block_idx << " " << val << endl;
    int borda = siz(idx)-1;
    cout << idx << " " << borda << endl;
    while(idx >= borda){
        cout << "initial block\n";
        if(arr[block_idx][idx] > 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()-1;
    }

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

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 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;
        x--;
        if(type == 0){
            insert(y, x);
            print();
        }else{
            int z = arr[x/raiz][x-siz(x)];
            cout << find(x, y+z) << endl;
        }
    }
    return 0;
}