#include<bits/stdc++.h> using namespace std; long long sum[100005][105],top,n,q,a[100005],ans; int main(){ scanf("%lld%lld",&n,&q); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); for(int j=0;j<=100;j++){ sum[i][j]=sum[i-1][j]; if(j<a[i])sum[i][j]++; } ans+=sum[i-1][a[i]]; } top=n; while(q--){ long long op,x; scanf("%lld",&op); if(op==2){ ans-=sum[top-1][a[top]]; for(int j=0;j<=100;j++)sum[top][j]=0; top--; printf("%lld\n",ans); } else{ top++; scanf("%lld",&x); a[top]=x; for(int j=0;j<=100;j++){ sum[top][j]=sum[max(0ll,top-1)][j]; if(j<x)sum[top][j]++; } ans+=sum[top-1][x]; printf("%lld\n",ans); } } return 0; }