#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;
}
}
if(nrc>100)
{
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;
}
else
{
vector<AIB> aib;
AIB temp(0);
aib.push_back(temp);
for(int i=1;i<=nrc;i++)
{
AIB temp(n);
aib.push_back(temp);
}
vector<set<int>> poz(nrc+1);
for(int i=0;i<n;i++)
{
aib[a[i]].update(i+1,1);
poz[a[i]].insert(i+1);
}
vector<int> ans(q,0);
for(int i=0;i<q;i++)
{
aib[a[x[i]]].update(x[i]+1,-1);
aib[v[i]].update(x[i]+1,1);
poz[a[x[i]]].erase(x[i]+1);
poz[v[i]].insert(x[i]+1);
a[x[i]]=v[i];
int maxi=0;
for(int j=1;j<=nrc;j++)
{
if(poz[j].empty()) continue;
int last=(*poz[j].rbegin());
if(last<maxi) continue;
maxi=last;
int sum=0;
for(int k=j+1;k<=nrc;k++)
{
sum+=aib[k].query(last);
}
ans[i]=max(ans[i],sum);
}
}
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;
}*/
