#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+5; int a[N],num[N],c[N]; int n,q; void add(int t)//计算a[t]对总逆序对数有什么贡献 { for(int i=1;i<t;i++) { if(a[i]>a[t])//构成逆序对 { num[t]++; } } } signed 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]; add(i); c[i]=c[i-1]+num[i];//计算a[1]到a[i]共有多少逆序对 } for(int i=1;i<=q;i++) { int tmp; cin>>tmp; if(tmp==1) { int x; cin>>x; a[n+1]=x;//加入一个数 cout<<c[n]+num[n+1]<<"\n"; c[n+1]=c[n]+num[n+1]; n++; } else { a[n]=0;//去掉最末尾的数 cout<<c[n-1]<<"\n"; c[n]=c[n-1]; n--; } } return 0; }