#include <bits/stdc++.h>

using namespace std;

struct node;
typedef node* ln;

struct node
{
	int pr;

	int v;
	int dp;

	int id,sz;
	
	ln l, r;

	node (int v=0) : pr(rand()),v(v),l(0),r(0) { upd(); }

	void upd()
	{
		dp = v;
		if (l) dp=max(dp,l->dp);		
		if (r) dp=max(dp,r->dp);
			
		sz = 1;
		if (l) sz+=l->sz;
		id = sz;		
		if (r) sz+=r->sz;		
	}
};

ln root;

void split ( ln t, int x, ln &l, ln &r)
{
	l=r=0;
	if (!t) return;
	if (t->id <= x)
	{
		split(t->r, x - t->id, t->r, r);
		l = t;
	} else
	{
		split(t->l, x, l, t->l);
		r = t;
	}

	t->upd();
}

ln merge(ln l, ln r)
{
	if (!l || !r) return (l?l:r);

	if (l->pr > r->pr)
	{
		l->r = merge(l->r, r);
		l->upd();
		return l;
	} else
	{
		r->l = merge(l,r->l);
		r->upd();
		return r;
	}
}

void insert(int x, int p)
{
	ln l,r;
	split(root,p,l,r);
	root = merge(merge(l,new node(x)),r);
}

void erase(int p)
{
	ln l,r,t;
	split(root,p,l,r);
	split(r,1,r,t);
	root = merge(l,t);
}

void show(ln t)
{
	if (!t) return;
	show(t->l);
	cout<<' '<<t->v;
	show(t->r);
}

int query(int x, int y)
{
	ln l,t,r;
	split(root, x, l, t);
	split(t, y-x+1, t, r);
	
	int m = t->dp;
	
	root = merge(merge(l,t),r);
	return m;
}

int main()
{
	ifstream cin("arbint.in");
	ofstream cout("arbint.out");
	
	srand(time(0));
	
	root = 0;
	
	int n,m;
	cin>>n>>m;
	for (int i=0; i<n; i++)
	{
		int x;
		cin>>x;
		insert(x,i);
	}
	
	while (m--)
	{
		int t,x,y;
		cin>>t>>x>>y;
		if (!t) cout<<query(x-1,y-1)<<'\n';
		else erase(x-1),insert(y,x-1);	
	}

    return 0;
}