#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
set<int> pos[1000009];
int seg[5000009],lazy[5000009];
void dawn(int node)
{
seg[2*node]+=lazy[node];
lazy[2*node]+=lazy[node];
seg[2*node+1]+=lazy[node];
lazy[2*node+1]+=lazy[node];
lazy[node]=0;
}
void update(int node,int tl,int tr,int l,int r,int v)
{
if(tr<l or r<tl) return;
if(l<=tl and tr<=r) seg[node]+=v,lazy[node]+=v;
else
{
dawn(node);
update(2*node,tl,(tl+tr)/2,l,r,v);
update(2*node+1,(tl+tr)/2+1,tr,l,r,v);
seg[node]=max(seg[2*node],seg[2*node+1]);
}
}
/*int get(int node,int tl,int tr,int i)
{
if(tr<i or i<tl) return -1603398;
else if(tl==tr) return seg[node];
dawn(node);
return max(get(2*node,tl,(tl+tr)/2,i),get(2*node+1,(tl+tr)/2+1,tr,i));
}*/
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V)
{
vector<int> num,res;
int n=A.size(),q=X.size();
for(int i=0;i<n;++i) num.push_back(A[i]);
for(int i=0;i<q;++i) num.push_back(V[i]);
sort(num.begin(),num.end());
num.resize(distance(num.begin(),unique(num.begin(),num.end())));
for(int i=0;i<n;++i)
{
A[i]=lower_bound(num.begin(),num.end(),A[i])-num.begin()+1;
pos[A[i]].insert(i);
}
for(int val,sum=0,i=1;i<=num.size();++i)
{
sum+=pos[i].size(); pos[i].insert(-1);
update(1,1,num.size(),i,i,*pos[i].rbegin()-sum+1);
}
for(int i=0;i<q;++i)
{
V[i]=lower_bound(num.begin(),num.end(),V[i])-num.begin()+1;
pos[A[X[i]]].erase(X[i]);
if(X[i]>*pos[A[X[i]]].rbegin()) update(1,1,num.size(),A[X[i]],A[X[i]],*pos[A[X[i]]].rbegin()-X[i]);
update(1,1,num.size(),A[X[i]],num.size(),1); A[X[i]]=V[i];
if(X[i]>*pos[A[X[i]]].rbegin()) update(1,1,num.size(),A[X[i]],A[X[i]],X[i]-*pos[A[X[i]]].rbegin());
update(1,1,num.size(),A[X[i]],num.size(),-1);
pos[A[X[i]]].insert(X[i]);
//for(int j=1;j<=num.size();++j) res.push_back(get(1,1,num.size(),j));
res.push_back(seg[1]);
}
return res;
}
/*
........................
..::-+**#%@@@@@@@@@@@@@@@@@@%#**+::..
..:=++#%%@@@@@@@@@@@@@@@@%%%%%%%%%@@@@@@@@@@@@%+.
..:-+*#%@@@@@@@@%%%%##############################%%@@@@*:.
..:-+*%@@@@@@@%%%##########################################%@@@@+:.
..:=+%@@@@@@%%#####################################################@@@@+..
....-+%@@@@@@%#############################################################@@@@=..
..=#@@@@@%%###################################################################%@@@%-.
.:+#%@@@@%%#########################################################################%@@@#:.
.:=*%@@@%%###############################################################################%@@@@-.
..-*%@@@%%#####################################################################################%@@@=.
..+@@@@###########################################################################################%@@@*..
.*@@@#*##############################################################################################@@@%.
.+@@@#**################################################################################################@@@%:.
.-%@@#**####%##############################################################################################%@@%:.
.+@@#***###%%################################################################################################%@@@-.
:#@%****###%%*#################################################################################################%@@@-.
-@@%****###@%*###################################################################################################%@@@-.
-@@#***###%@#*#####################################################################################################%@@@=.
-@@#***###@@#*#######################################################################################################@@@%-.
:@@#***###@%**#########################################################################################################@@@+.
:%@#***##%@%**##########################################################################################################%@@@.
.#@%***##%@%**############################################################################################################%@@*.
.+@%***##@@#**##############################################################################################@@##############@@@:.
:@@***##@@#**###############################################################################################@@@%############%@@#.
.%@#***#@@#**####################################%@@%#######################################################@@@@@@############@@@=.
.*@%***%@@#***##################################%@@@@@@@%###################################################%@@@@@@@############@@%.
-@@***%@@#***##################################@@@@@@@@@@@%#################################################@@@@@@@@@###########@@@=.
.#@#**#@@#****################################%@@@@@@@@@@@@@@@%#############################################%@@@@@@@@@@###########@@%.
=@%**#@@%****################################@@@@@@@@@@@@@@@@@@@%###########################################@@@@@@@@@@@@##########%@@=.
.@@**#@@%*****##############################%@@@@@@@@@@@@@@@@@@@@@@@########################################@@@@@@@@@@@@@@##########@@%.
.#@###@@%*****##############################@@@@@@@@@@@@@@@@@@@@@@@@@@@#####################################@@@@@@@@@@@@@@@@#########@@@-
..#@###%@@******############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##################################%@@@@@@@@@@@@@@@@@#########@@#.
.-%@###%@@#*****############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############################%@@@@@@@@@@@@@@@@@@@########@@@:.
...-%@%####@@#******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%############################%@@@@@@@@@@@@@@@@@@@@%#######%@@*.
..:+%@@######%@%******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##########################@@@@@@@@@@@@@@@@@@@@@@%#######@@@.
.#@%%%##########@@*******#########################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######################%@@@@@@@@@@@@@@@@@@@@@@@@%######%@@+.
:#@%##########@@#******#########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@####################%@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@%.
.+%@%#######%@%*******########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@-.
.+%@@%####@@#******#######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######@@#.
.:*%@@@@@%*******######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####%@@:.
.....-@@********#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####@@*.
.=@%*******#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@@.
.%@#*******####################@@@@@@@@@@@@@@@@@@@@@@@@@@%##*******##%@@@@@@@@@@@@@@@@@@@@@@####%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@=.
.+@@********###################@@@@@@@@@@@@@@@@@@@@@@#*=:...............:=*#@@@@@@@@@@@@@@@@@@#%@@@@@@@@@@@@@@#*+-:.......:-=+#%@@@@@@@@@%####@@%.
.@@%*******###################@@@@@@@@@@@@@@@@@@@@#-.........................-*%@@@@@@@@@@@@@@@@@@@@@@@@@@%*-....................=#@@@@@@@#####@@=.
.+@@********##################@@@@@@@@@@@@@@@@@@@=...............................-%@@@@@@@@@@@@@@@@@@@@@@%-..........................=@@@@@@####@@%.
:@@@********#################@@@@@@@@@@@@@@@@@@=...................................-@@@@@@@@@@@@@@@@@@@@-..............................+@@@@%####@@+.
.*@@#********################%@@@@@@@@@@@@@@@@#:..........................:=+++=:....:*@@@@@@@@@@@@@@@@*:....:=+++=:.....................:%@@@####%@@:.
:@@@********################%@@@@@@@@@@@@@@@@*...........................=*#%%%#*=.....+@@@@@@@@@@@@@@=.....-*#%%%#*-.....................:#@@%####@@#.
.*@@%********###############%@@@@@@@@@@@@@@@@#...........................-*%@@@@@%*-.....*@@@@@@@@@@@@+.....-*%@@@@@#*-.....................:@@@####%@@*.
.=@@@*********###############@@@@@@@@@@@@@@@@@:...........................*=-@@@@@@#*.....:@@@@@@@@@@@@......*=+@@@@@@*+......................=@@@####@@@=.
-@@@**********##############@@@@@@@@@@@@@@@@@#............................*..+@@@@@#*......#@@@@@@@@@@*.....:*..#@@@@@#*......................:@@@%####@@@=.
.+@@@#**********#############%@@@@@@@@@@@@@@@@@*............................+-.%@@@@@*+......#@@@@@@@@@@+......*:.%@@@@@*+.......................@@@@#####@@@=.
.-%@@@***********##############@@@@@@@@@@@@@@@@@@#............................-*#@@@@@#*:......%@@@@@@@@@@+......=*#@@@@@#*:......................:@@@@%#####@@@+.
..=#@@@#************#############@@@@@@@@@@@@@@@@@@@@:............................-+*###*+:......:@@@@@@@@@@@#.......=*#%%#*+:.......................=@@@@@######@@@#.
...:=*@@@%#*************#############%@@@@@@@@@@@@@@@@@@@@*..............................:===:........#@@@@@@@@@@@@-.......:=++=-.........................%@@@@@@######@@@%-.
.-+*%@@@@%#****************#############@@@@@@@@@@@@@@@@@@@@@@=.........................................+@@@@@@@@@@@@@@:....................................#@@@@@@@#######%@@@*..
-@@%**********************#############%@@@@@@@@@@@@@@@@@@@@@@@+.......................................#@@@@@@@@@@@@@@@@:..................................#@@@@@@@@@########@@@@=.
.:%@%********************##############@@@@@@@@@@@@@@@@@@@@@@@@@%-...................................=@@@@@@@@@@@@@@@@@@@*...............................=@@@@@@@@@@@%########%@@@%+.
.+@@#******************##############@@@@@@@@@@@@@@@@@@@@@@@@@@@#=..............................:+%@@@@@@@@@@@@@@@@@@@@@%+:..........................=#@@@@@@@@@@@@@##########%@@@@*:.
.:%@@#****************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%+-........................:=*@@@@@@@@@%%@@@@@@@@@@%@@@@@*-:....................-+@@@@@@@@@@@@@@@@%###########%@@@+.
.+@@%***************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*=-:..............::-+#@@@@@@@%#+-:::-#@@@@@@#::-+#@@@@@#=-::.........::-=*@@@@@@@@@@@@@@@@@@@@##########%@@@+.
.#@@%*************#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#*++++++*#%@@@@@@@@@@%=:::::::::::+@@@=:::::::-#@@@@@@@@@%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@%########%@@@=.
.-%@@%************############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=-:::::::::::::::-:::::::::::-=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######@@@@-.
..=%@@%**********############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+-:::::::::::::::::::::::::::::::::=%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@#:.
.=%@@%*********###########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=:::::::::::::::-+####=::::::::::::::::+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######@@@@=..
.=%@@%#*******############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=::::::::::::::::+#+-::=#*::::::::::::::::-#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@%-.
.=%@@@#******#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+:::::::::::::::::*-:::::::*+:::::::::::::::::*@@@@@@@@@@@@@@@@@@@@@@@@@@@%######%@@@+..
.-%@@@%*****###############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#::::::::::::::::::-::::::::::=::::::::::::::::::=@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@:.
..-#@@@@#***################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@@@@%######@@@@+..
.:+@@@@%#**################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%-::::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@%######%@@@*:.
..=#@@@@#**################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#:::::::::::::::::::::::::::::::::::::::::::::::::::::::=@@@@@@@@@@@@@@@@%######%@@@#-.
.:*%@@@%###################%@@@@@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::+@@@@@@@@@@@@@%#######@@@%=..
.-#@@@@%###################%@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::-=@@@@@@@@@@@%######%@@@%=..
...-%@@@@@####################@@@@@@@@@@@@@@@@@@@@+::::::::::::::::::::::::::::::::::::::::::::::::::::::-#@@@@@@@@@@@%######%@@@%-..
...-#@@@@@%###################%@@@@@@@@@@@@@@@@@@@#+:::::::::::::::::::::::::::::::::::::::::::::::+%@@@@@@@@@@@%######%@@@@*:..
..:-*@@@@@@%%##################%@@@@@@@@@@@@@@@@@@%#+=:::::::::::::::::::::::::::::::::::::=*#%@@@@@@@@@@@%######%@@@@@#=..
..-+#@@@@@@%%##################%%@@@@@@@@@@@@@@@@@@%*+==-:::::::::::::::::::::::-=+*#%@@@@@@@@@@@@@%######%@@@@@*-:..
..=#%@@@@@@%%###################%@@@@@@@@@@@@@@@@@@@@@%#*+===------===+*#%@@@@@@@@@@@@@@@@@@%######%@@@@@%*-.
..-*@@@@@@@@@%####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######%@@@@@@#-..
.....=#@@@@@@@@@@%######################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%########%@@@@@@%+:...
..::=*%@@@@@@@@@@%%#######################%%%%%@@@@@@@@@@@@%%%%############%@@@@@@@%=:..
...-=+#%@@@@@@@@@@@@%%%##########################################%%@@@@@@%*=-:..
...:-+*#%@@@@@@@@@@@@@@%%%%%#########################%%%@@@@@@@%*=:..
...*@@%@@@@@@@@@@@@@@@@@@@@@@@%%%%%%####%%@@@@@@@@%#+:..
.*@@****#####%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=:..
.@@%****##########@#====%%###@##@%%%@@@%-:....
-@@#****##########@#===+@#***@%=@%###@@%.
=@@*****##########%@===#@#***%@=%@###%@@-
.*@@*****###########@*==*%%%%%@@+@%###%@@+.
.@@%****############%@+=====++==%@#####@@%.
=@@#****#############@@========#@######@@@.
.*@@*****############@@%@+=====*@#######@@@=.
.%@@*****###########%@##@@#===#@########%@@*.
-@@%****###########%@%##@%%%*#@##########@@%.
=@@#****###########@%###@##%@@###########@@@-.
+@@*****##########@@###%@##%@@###########@@@+.
.%@@****##########@@####@%##%@@###########%@@%.
-@@%****#########@@#####@###%@@############@@@:
=@@#****########%@#####%@####@@############@@@=.
#@@*****#######%@######@%####@@############%@@#.
.%@@****#######%@######%@#####@@############%@@%.
-@@%****######%@#######%@#####@@%############@@@-.
=@@#****#####%@########@%#####@@%############@@@+.
+@@#****####%@########%@######@@%############%@@#.
.%@@****####%@#########@@######@@%############%@@@:
:@@%****###%@##########@%######@@%#############@@@=.
=@@%****##%%##########%@#######@@%#############@@@*.
#@@#****#%%###########@@#######@@@#############%@@%.
.%@@*****%############%@%#######@@@#############%@@@:
-@@@****##############@@########%@@##############@@@+.
-@@%****##############@%########%@@##############@@@#.
.*@@#****#############@@#########%@@##############%@@@:
.%@@*****#############@%#########%@@##############%@@@-.
:@@@*****############%@##########%@@###############@@@*.
-@@%*****############@%##########%@@###############@@@%.
#@@#****############%@############@@###############%@@@:
.%@@#****############@%############@@%###############@@@=.
:@@@*****###########%@#############@@%###############@@@*.
-@@%*****###########@%#############@@%###############@@@%.
=@@%*****##########%@##############@@%###############%@@@:
.#@@#*****##########@%##############@@%################@@@+.
:@@@*****###########@###############@@%################@@@#.
*/
