#include <bits/stdc++.h>
using namespace std;
class AIB
{
private:
vector<int> aib;
int n;
int lsb(int x)
{
return x&(-x);
}
public:
AIB(int siz) :aib(siz+1,0)
{
n=siz;
}
void update(int poz,int val)
{
for(int i=poz;i<=n;i+=lsb(i))
{
aib[i]+=val;
}
return;
}
int query(int poz)
{
int sol=0;
for(int i=poz;i>=1;i-=lsb(i))
{
sol+=aib[i];
}
return sol;
}
};
vector<int> countScans(vector<int> a,vector<int> x,vector<int> v)
{
int n=a.size(),q=x.size();
map<int,vector<pair<int,int>>> nrm;
for(int i=0;i<n;i++) nrm[a[i]].push_back({i,0});
for(int i=0;i<q;i++) nrm[v[i]].push_back({i,1});
int nrc=0;
for(auto [val,V]:nrm)
{
nrc++;
for(auto [id,tip]:V)
{
if(tip==0) a[id]=nrc;
else v[id]=nrc;
}
}
AIB aib(nrc);
vector<int> ans(q,0);
for(int i=0;i<q;i++)
{
a[x[i]]=v[i];
for(int j=0;j<n;j++)
{
ans[i]=max(ans[i],aib.query(nrc)-aib.query(a[j]));
aib.update(a[j],1);
}
for(int j=0;j<n;j++) aib.update(a[j],-1);
}
return ans;
}
/*int main()
{
int n,q;
cin>>n>>q;
vector<int> a(n),x(q),v(q);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<q;i++) cin>>x[i]>>v[i];
vector<int> ans=countScans(a,x,v);
for(int x:ans) cout<<x<<'\n';
return 0;
}*/
