#include <fstream>
#include <iostream>
#include <random>
#include <set>

using namespace std;

ifstream fin("rotatii.in");
ofstream fout("rotatii.out");

mt19937 gen(151121);

const int inf = 0x3f3f3f3f;

int n, m;

struct treap {
    int val, prio, sz, minpoz;
    long long sum, minsum;
    treap *left, *right;
};
treap *root;
void init(treap *root, int val, int poz)
{
    root->val = val;
    root->prio = gen();
    // cout << root->val << ' ' << root->prio << '\n';
    root->sz = 1, root->sum = val, root->minsum = val, root->minpoz = poz;
    root->left = NULL, root->right = NULL;
}

int get_size(treap *root)
{
    if(root == NULL)
        return 0;
    return root->sz;
}

long long get_sum(treap *root)
{
    if(root == NULL)
        return 0;
    return root->sum;
}

long long get_minsum(treap *root)
{
    if(root == NULL)
        return inf;
    return root->minsum;
}

int get_minpoz(treap *root)
{
    if(root == NULL)
        return 0;
    return root->minpoz;
}



void update_treap(treap *root)
{
    if(root == NULL)
        return;
    root->sz = get_size(root->left) + get_size(root->right) + 1;
    root->sum = get_sum(root->left) + get_sum(root->right) + root->val;
    root->minsum = get_minsum(root->left);
    root->minpoz = get_minpoz(root->left);
    if(get_sum(root->left) + root->val  <  root->minsum)
    {
        root->minsum = get_sum(root->left) + root->val;
        root->minpoz = get_size(root->left) + 1;
    }
    if(get_sum(root->left) + root->val + get_minsum(root->right)  <  root->minsum)
    {
        root->minsum = get_sum(root->left) + root->val + get_minsum(root->right);
        root->minpoz = get_size(root->left) + 1 + get_minpoz(root->right);
    }
}

void split_treap(treap *root, treap *&left, treap *&right, int poz)
{
    if(root == NULL)
    {
        left = NULL;
        right = NULL;
        return;
    }
    update_treap(root);
    if(get_size(root->left) < poz)
    {
        split_treap(root->right, root->right, right, poz - get_size(root->left) - 1);
        left = root;
    }
    else
    {
        split_treap(root->left, left, root->left, poz);
        right = root;
    }
    update_treap(root);
}

void merge_treap(treap *&root, treap *left, treap *right)
{
    if(left == NULL)
    {
        root = right;
        update_treap(root);
        return;
    }
    if(right == NULL)
    {
        root = left;
        update_treap(root);
        return;
    }
    if(left->prio > right->prio)
    {
        merge_treap(left->right, left->right, right);
        root = left;
    }
    else
    {
        merge_treap(right->left, left, right->left);
        root = right;
    }
    update_treap(root);
}

void insert_treap(int val, int poz)
{
    treap *left, *right;
    treap *curr = new treap;
    init(curr, val, poz);
    split_treap(root, left, right, poz - 1);
    merge_treap(left, left, curr);
    merge_treap(root, left, right);
}

void erase_treap(int poz)
{
    treap *left, *right, *aux;
    split_treap(root, left, right, poz - 1);
    split_treap(right, aux, right, 1);
    merge_treap(root, left, right);
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int x;
        fin >> x;
        insert_treap(x, i);
    }
    for(int i = 1; i <= m; i++)
    {
        int op, x, y;
        fin >> op;
        if(op == 0)
        {
            fin >> x >> y;
            insert_treap(y, x + 1);
        }
        if(op == 1)
        {
            fin >> x;
            erase_treap(x);
        }
        if(op == 2)
        {
            if(get_sum(root) < 0)
                fout << "-1\n";
            else
                fout << get_minpoz(root) % get_size(root) << '\n';
        }
    }
    return 0;
}