#include "bubblesort2.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int n;
int a[500005];
int init[500005];
/*struct node
{
int val;
int lazy;
int tole;
int tori;
};
vector<node> aint[2000005];
void propagate_mare(int nod)
{
}
void propagate_mic(int nod, int c)
{
}
void upd_mare_plus(int nod, int st, int dr, int le, int ri, int newv)
{
}
void upd_mic_plus(int nod, int st, int dr, int le, int ri, int newv, int c)
{
}
void upd_mare_egal(int nod, int st, int dr, int le, int ri, int newv)
{
}
void upd_mic_egal(int nod, int st, int dr, int le, int ri, int newv, int c)
{
}*/
pair<int,int> v[500005];
int calcmax()
{
for(int i=0;i<n;i++)
{
v[i] = {a[i],i};
}
sort(v,v+n);
int mxm=0;
for(int i=0;i<n;i++)
{
mxm = max(mxm, v[i].second - i);
}
return mxm;
}
ordered_set s;
set<int> pozs[105];
std::vector<int> countScans(std::vector<int> A, std::vector<int> qp, std::vector<int> qv)
{
int q=qp.size();
n=A.size();
for(int i=0;i<n;i++)
a[i]=A[i];
std::vector<int> answer(q);
if(n<=8000)
{
for(int i=0;i<q;i++)
{
a[qp[i]] = qv[i];
answer[i] = calcmax();
}
}
else
{
for(int i=0;i<n;i++)
{
s.insert({a[i],i});
pozs[a[i]].insert(i);
}
for(int i=0;i<q;i++)
{
pozs[a[qp[i]]].erase(qp[i]);
s.erase({a[qp[i]],qp[i]});
a[qp[i]] = qv[i];
s.insert({a[qp[i]],qp[i]});
pozs[a[qp[i]]].insert(qp[i]);
int mxm=0;
for(int j=0;j<=100;j++)
{
if(pozs[j].empty())
continue;
auto it = pozs[j].rbegin();
int x = *it;
//for(auto x:pozs[j])
mxm = max(mxm, x - (int)s.order_of_key({a[x],x}));
}
answer[i] = mxm;
}
}
return answer;
}
/**
4 2
1 2 3 4
0 3
2 1
*/
