#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x)
{
    x=0;char c=getchar();bool f=0;
    for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c-'0');
    x=(f?-x:x);
}
const int N = 2e5+7;
const int D1 = 550;
const int D2 = 350;
const int B1 = N/D1+3;
const int B2 = N/D2+3;
int n,m;
int bel1[N],st1[N],ed1[N],C1;
int bel2[N],st2[N],ed2[N],C2;
short val[B2+2][N];
struct DS
{
    short state[B2+2];
    int sum[B2+2];
    void upd(int x)
    {
        for(int i=bel2[x]+1;i<=C2;i++)sum[i]++;
        int t=++state[bel2[x]];
        for(int i=st2[bel2[x]];i<=ed2[bel2[x]];i++)val[t][i]=val[t-1][i]+(i>=x);
    }
    inline int qry(int x){return sum[bel2[x]]+val[state[bel2[x]]][x];}
}H[N];
typedef long long LL;
int a[N],c[N];
LL w[N];
struct BIT
{
    int tr[N];
    void upd(int x,int v){for(int i=x;i<=n;i+=i&-i)tr[i]+=v;}
    int ask(int x){int res=0;for(int i=x;i;i-=i&-i)res+=tr[i];return res;}
}T[B1+2],F;
LL cnt[B1+2][B2+2];
int pos[N];
vector<int> mod[B1+2];
int main()
{
    read(n);read(m);
    for(int i=1;i<=n;i++)read(a[i]),pos[a[i]]=i;
    for(int i=1;i<=n;i++)
    {
        bel1[i]=(i-1)/D1+1;ed1[bel1[i]]=i;if(!st1[bel1[i]])st1[bel1[i]]=i;
        bel2[i]=(i-1)/D2+1;ed2[bel2[i]]=i;if(!st2[bel2[i]])st2[bel2[i]]=i;
    }
    C1=bel1[n];
    C2=bel2[n];
    for(int i=1;i<=n;i++)
    {
        H[i]=H[i-1];
        H[i].upd(a[i]);
        c[i]=H[i].qry(a[i]);
    }
    while(m--)
    {
        int opt;
        read(opt);
        if(opt==1)
        {
            int l,r;
            read(l);read(r);
            F.upd(l,1);F.upd(r+1,-1);
            if(bel1[l]==bel1[r])for(int i=l;i<=r;i++)w[i]+=H[l-1].qry(a[i]);
            else
            {
                int L=bel1[l],R=bel1[r];
                for(int i=l;i<=ed1[L];i++)w[i]+=H[l-1].qry(a[i]);
                for(int i=st1[R];i<=r;i++)w[i]+=H[l-1].qry(a[i]);
                for(int i=L+1;i<=R-1;i++)mod[i].push_back(n-l+2);
                for(int o=1;o<=C2;o++)
                {
                    int v=H[l-1].qry(st2[o]-1);
                    cnt[L+1][o]+=v;
                    cnt[R][o]-=v;
                }
            }
        }
        else
        {
            int x;
            read(x);
            LL ans=1ll*F.ask(x)*c[x]-w[x];
            for(int u=bel1[x];u>=1;u--)ans-=cnt[u][bel2[a[x]]];
            if(!mod[bel1[x]].empty())
            {
                for(int l:mod[bel1[x]])T[bel1[x]].upd(l,1);
                mod[bel1[x]].clear();
            }
            for(int i=a[x]-1;i>=st2[bel2[a[x]]];i--)
            {
                int r=pos[i];
                if(r<x)
                {
                    ans-=T[bel1[x]].ask(n-r+1);
                }
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}