#include<bits/stdc++.h>
#define ll int
#define N 200005
using namespace std;
inline char nc(){
	static char buf[1000000],*p=buf,*q=buf;
	return p==q&&(q=(p=buf)+fread(buf,1,1000000,stdin),p==q)?EOF:*p++;
}
inline ll read(){
	ll res = 0,w = 1;
	char c = nc();
	while(c<'0'||c>'9')w=(c=='-'?-1:w),c=nc();
	while(c<='9'&&c>='0')res=res*10+c-'0',c=nc();
	return res*w;
}
char obuf[1<<21],*p3=obuf; 
inline void pc(char c){ 
	p3-obuf<=(1<<20)?(*p3++=c):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=c); 
} 
inline void write(long long x){ 
	if(x<0) pc('-'),x=-x; 
	if(x>9) write(x/10); 
	pc(x%10+'0'); 
}
ll n,m,i,j,a[N],opt[N],l[N],r[N],x[N],K,id[N],ls[N],rs[N],now,tr[N],cnt[N],qzh[N],cntt[N],tr2[N];
long long ans[N];
inline void add(ll k,ll x,ll n,ll *tr){while(k<=n) tr[k]+=x,k+=k&(-k);}
inline ll query(ll k,ll *tr){
    ll num = 0;
    while(k) num+=tr[k],k-=k&(-k);
    return num;
}
inline void solve(ll idd){
    ll lt = ls[idd],rt = rs[idd];
    for(ll i=1;i<=n;i++) qzh[i]=0;
    for(ll i=lt;i<=rt;i++) qzh[a[i]]++,add(a[i],1,n,tr),cntt[i]=query(a[i],tr);
    for(ll i=lt;i<=rt;i++) add(a[i],-1,n,tr);
    for(ll i=1;i<=n;i++) qzh[i]+=qzh[i-1];
    ll nums = 0,num = 0;
    for(ll i=1;i<=m;i++){
        if(opt[i]==1){
            if(id[l[i]]==id[r[i]]) continue;
            if(id[l[i]]<idd&&idd<id[r[i]]){
                nums++,num++;
                add(r[i],1,n,tr);
            }
            if(idd==id[l[i]]+1) for(ll j=l[i];j<=rs[id[l[i]]];j++) add(a[j],1,n,tr2);
            if(idd==id[r[i]]) for(ll j=l[i];j<=rs[id[l[i]]];j++) add(a[j],-1,n,tr2);
        }
        else{
            if(lt<=x[i]&&x[i]<=rt) ans[i]+=1ll*cntt[x[i]]*nums;
            else if(x[i]>rt){
                ll cnt = num-query(x[i]-1,tr);
                ans[i]+=1ll*cnt*qzh[a[x[i]]];
            }
            if(id[x[i]]>=idd){
                ans[i]+=query(a[x[i]],tr2);
            }
        }
    }
    for(ll i=1;i<=n;i++) tr[i]=0,tr2[i]=0;
}
int main(){
    ll c1 = clock();
	n=read(),m=read(),K=sqrt(n);
    for(i=1;i<=n;i++) a[i]=read();
    for(i=1;i<=m;i++){
        opt[i]=read();
        if(opt[i]==1) l[i]=read(),r[i]=read();
        else x[i]=read();
    }
    for(i=1,now=1;i<=n;i++){
        id[i]=now;
        if(!ls[id[i]]) ls[id[i]]=i;
        rs[id[i]]=i;
        if(i%K==0) now++;
    }
    for(i=1;i<=m;i++){
        if(opt[i]==1){
            if(id[l[i]]==id[r[i]]){
                for(j=l[i];j<=r[i];j++){
                    add(a[j],1,n,tr);
                    cnt[j]+=query(a[j],tr);
                }
                for(j=l[i];j<=r[i];j++) add(a[j],-1,n,tr);
            }
            else{
                for(j=l[i];j<=rs[id[l[i]]];j++) add(a[j],1,n,tr),cnt[j]+=query(a[j],tr);
                for(j=ls[id[r[i]]];j<=r[i];j++) add(a[j],1,n,tr),cnt[j]+=query(a[j],tr);
                for(j=l[i];j<=rs[id[l[i]]];j++) add(a[j],-1,n,tr);
                for(j=ls[id[r[i]]];j<=r[i];j++) add(a[j],-1,n,tr);
            }
        }
        if(opt[i]==2) ans[i]+=cnt[x[i]];
    }
    for(i=1;i<=id[n];i++) solve(i);
    for(i=1;i<=m;i++) if(opt[i]==2) write(ans[i]),pc('\n');
    ll c2 = clock();
    cerr<<"time is "<<c2-c1<<endl;
	return fwrite(obuf,p3-obuf,1,stdout),0;
}