#include<bits/stdc++.h> using namespace std; int n,q,a[500010],c[500010]; long long ans; void msort(int l,int r) { ans=0; if(l==r) { return; } int mid=(l+r)/2,i=l,j=mid+1,k=l; msort(l,mid); msort(mid+1,r); while(i<=mid&&j<=r) { if(a[i]<=a[j]) { c[k++]=a[i++]; } else { c[k++]=a[j++]; ans+=mid-i+1; } } while(i<=mid) { c[k++]=a[i++]; } while(j<=r) { c[k++]=a[j++]; } for(int i=l;i<=r;i++) { a[i]=c[i]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>q; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=q;i++) { int tmp,x; cin>>tmp; if(tmp==1) { cin>>x; a[++n]=x; msort(1,n); cout<<ans<<"\n"; } else { a[n--]=0; msort(1,n); cout<<ans<<"\n"; } } return 0; }