bool M1;
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define LL __int128
#define db long double
#define LD long double
#define Pii pair<int,int>
#define Pll pair<ll,ll>
#define Pull pair<ull,ull>
#define fir first
#define sec second
#define vec vector<int>
#define pb push_back
#define qlr cerr<<"qlr\n"
#define dyh cerr<<"dyh\n"
#define pc(x) __builtin_popcount(x)
#define uni(x,y) uniform_int_distribution<int>(x,y)(rng)
#define unl(x,y) uniform_int_distribution<ll>(x,y)(rng)
#define unr(x,y) uniform_real_distribution<double>(x,y)(rng)
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define look_memory cerr<<'\n'<<abs(&M1-&M2)/1024.0/1024<<'\n'
#define look_time cerr<<'\n'<<clock()*1.0/CLOCKS_PER_SEC<<'\n'
mt19937 rng(time(0)^(*new int));
const ll INF=0x3f3f3f3f3f3f3f3f;
int Mod;
template<typename T>
inline void inc(T &a,T b){
	if(b<0) b+=Mod;
	a+=b;
	if(a>=Mod) a-=Mod;
}
template<typename T>
inline void dec(T &a,T b){
	if(b<0) b+=Mod;
	a-=b;
	if(a<0) a+=Mod;
}
template<typename T>
inline void muc(T &a,T b){
	a=a*b%Mod;
}
template<typename T>
inline bool chkmin(T &a,T b){
	if(a<=b) return false;
	a=b;
	return true;
}
template<typename T>
inline bool chkmax(T &a,T b){
	if(a>=b) return false;
	a=b;
	return true;
}
int n,q,sq=447,tot;
bool vis[200010];
int a[200010];
int g1[200010];
int g2[510][200010];
int w[200010];
ll ans[200010];
struct Qry{
	int a,b,num;
};
Qry qry[20000010];
int id(int x){
	return (x-1)/sq+1;
}
int l(int x){
	return (x-1)*sq+1;
}
int r(int x){
	return min(x*sq,n);
}
struct Bit{
	#define N 200000
	int w[N+10];
	void clear(){
		memset(w,0,sizeof(w));
	}
	int lb(int x){
		return x&-x;
	}
	void add(int x,int y){
		for(int i=x;i<=N;i+=lb(i)) w[i]+=y;
	}
	int query(int x){
		int res=0;
		for(int i=x;i;i-=lb(i)) res+=w[i];
		return res;
	}
	#undef N
}bit; 
struct Blk1{
	#define N 200000
	#define sq 447
	#define B N/sq
	int w[N+10],tag[N+10];
	void clear(){
		memset(w,0,sizeof(w));
		memset(tag,0,sizeof(tag));
	}
	int id(int x){
		return (x-1)/sq+1;
	}
	int l(int x){
		return (x-1)*sq+1;
	}
	int r(int x){
		return min(x*sq,n);
	}
	void add(int x,int y,int z){
		if(id(x)==id(y)){
			F(i,x,y) w[i]+=z;
			return;
		}
		F(i,x,r(id(x))) w[i]+=z;
		F(i,l(id(y)),y) w[i]+=z;
		F(i,id(x)+1,id(y)-1) tag[i]+=z;
	}
	int query(int x){
		return w[x]+tag[id(x)];
	}
	#undef N
}blk1;
struct Blk{
	#define N 200000
	#define sq 447
	#define B N/sq
	int w[N+10],sum[B+10];
	queue<int> q;
	int id(int x){
		return (x-1)/sq+1;
	}
	int l(int x){
		return (x-1)*sq+1;
	}
	int r(int x){
		return min(x*sq,n);
	}
	void clear(){
		while(!q.empty()){
			int x=q.front();q.pop();
			w[x]=0;
			sum[id(x)]=0;
		}
	}
	void add(int x,int y){
		q.push(x);
		w[x]+=y;
		sum[id(x)]+=y;
	}
	int query(int x){
		int res=0;
		F(i,1,id(x)-1) res+=sum[i];
		F(i,l(id(x)),x) res+=w[i];
		return res;
	}
	#undef N
	#undef sq
	#undef B
}blk2;
void change(int x,int y,int num){
	bit.add(x,1);
	bit.add(y+1,-1);
	x=x-1;
	if(!x) return;
	blk1.add(x,n,1);
	F(i,l(id(x)),x) qry[++tot]={x+1,a[i],-1},qry[++tot]={y+1,a[i],-2};
}
void query(int x,int num){
	vis[num]=1;
	ans[num]=1ll*bit.query(x)*g1[x];
	F(i,1,id(x)-1) ans[num]-=1ll*(blk1.query(x-1)-blk1.query(r(i)))*g2[i][x];
	qry[++tot]={x,a[x],num};
}
void cdq(int L,int R){
	if(L==R) return;
	int mid=(L+R)>>1;
	cdq(L,mid);
	cdq(mid+1,R);
	
	blk2.clear();
	for(int i=mid+1,j=L;i<=R;i++){
		if(qry[i].num<0) continue;
		while(j<=mid&&qry[i].a>=qry[j].a){
			if(qry[j].num<0) blk2.add(qry[j].b,qry[j].num==-1?1:-1);
			j++;
		}
		ans[qry[i].num]-=blk2.query(qry[i].b);
	}
	
	sort(qry+L,qry+R+1,[&](Qry cm1,Qry cm2){return cm1.a<cm2.a;});
}
bool M2;
int main(){
//	freopen("years.in","r",stdin);
//	freopen("years.out","w",stdout);
	srand(time(0)^(*new int));
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	F(i,1,n) cin>>a[i];
	
	bit.clear();
	F(i,1,n){
		bit.add(a[i],1);
		g1[i]=bit.query(a[i]);
	}
	F(i,1,id(n)){
		blk1.clear();
		F(j,l(i),r(i)) blk1.add(a[i],n,1);
		F(j,r(i)+1,n) g2[i][j]=blk1.query(a[j]);
	}
	
	bit.clear();
	blk1.clear();
	F(i,1,q){
		int op,x,y;
		cin>>op;
		if(op==1) cin>>x>>y,change(x,y,i);
		else cin>>x,query(x,i);
	}
	
	cdq(1,tot);
	F(i,1,q) if(vis[i]) cout<<ans[i]<<'\n';
	look_memory;
	look_time;
	return 0;
}
/*
8 4
5 4 8 7 1 6 3 2
1 2 5
1 2 8
1 7 8
2 4
*/