fila_seg_bit

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

using namespace std;
typedef long long ll;

struct q{
    int type, pos;
    ll val;
    q(int _type, int _pos, ll _val) : type(_type), pos(_pos), val(_val){}
};
ll bit[2][MAX], seg[4*MAX], h[MAX], freq[MAX], n;

void bit_update(int id, int idx, ll val){
    idx = idx + 1;
    for(; idx <= MAX; idx += idx&(-idx)) bit[id][idx] += val;
}

ll sum(int id, int idx){
    idx = idx + 1;
    ll ans = 0;
    for(; idx > 0; idx -= idx&(-idx)) ans +=  bit[id][idx];
    return ans;
}

void update(int id, int l, int r, int idx, ll val){
    if(r < idx || idx < l) return;
    else if(l == r) seg[id] = val;
    else{
        int mid = (l+r)/2;
        update(2*id, l, mid, idx, val);
        update(2*id+1, mid+1, r, idx, val);

        seg[id] = max(seg[2*id], seg[2*id+1]);
    }
}

ll search(int id, int l, int r, int idx, ll val){
    int mid = (l+r)/2;

    if(seg[id] <= val) return 0;
    if(idx < l) return 0;

    if(l == r) return l;

    if(idx < r){
        return max(search(2*id, l, mid, idx, val),
                   search(2*id+1, mid+1, r, idx, val));
    }

    if(seg[2*id+1] > val) return search(2*id+1, mid+1, r, idx, val);
    return search(2*id, l , mid, idx, val);
}

ll busca_binaria(int idx){
    int l = 1, r = n;
    while(l < r){
        int mid = (l + r)/2;
        if(sum(0, mid) >= idx) r =  mid;
        else l = mid+1;
    }

    return r;
}

int print_tree(){
    for(int i = 0; i <= 4*n; i++) cout << seg[i] << " \n"[i == 4*n];
}
vector<q> consultas;
int main(){
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++) {
        int val; scanf("%d", &val);
        consultas.emplace_back(0, i, val);
        bit_update(1, i, 1);
        freq[i]++;
    }
    int cases; scanf("%d", &cases);
    for(int i = 0; i < cases; i++){
        int type, x;
        ll y; scanf("%d %d %lld", &type, &x, &y);
        consultas.emplace_back(type, x, y);
        if(type == 0){
            bit_update(1, x, 1);
            n++;
            freq[x]++;
        }
    }

    for(int i = 0; i < consultas.size(); i++){
        q actual = consultas[i];
        if(actual.type == 0){
            freq[actual.pos]--;
            int pos = sum(1, actual.pos)-freq[actual.pos];
            update(1, 1, n, pos, actual.val);
            h[pos] = actual.val;
            bit_update(0, pos, 1);
        }else{
            int pos = busca_binaria(actual.pos);

            cout << pos << endl;
            ll maior = search(1, 1, n, pos, h[pos] + actual.val);
            if(maior == 0) printf("0\n");
            else printf("%lld\n", sum(0,maior));
        }
    }
    return 0;
}