#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
int n,q;
vector<int> comp,v,x,y;
inline void compress(){
for(const auto& i:v)comp.push_back(i);
for(const auto& i:y)comp.push_back(i);
sort(comp.begin(),comp.end());
comp.resize(unique(comp.begin(),comp.end())-comp.begin());
for(auto& i:v)i=lower_bound(comp.begin(),comp.end(),i)-comp.begin();
for(auto& i:y)i=lower_bound(comp.begin(),comp.end(),i)-comp.begin();
}
inline int solve(){
//cerr<<"s: ";for(const auto& i:v)cerr<<i<<" ";cerr<<endl;
vector<int> first,last,sorted;
first.assign(comp.size(),-1);
last.assign(comp.size(),-1);
sorted=v;
sort(sorted.begin(),sorted.end());
for(int i=0;i<n;i++){
if(first[sorted[i]]==-1)first[sorted[i]]=i;
last[sorted[i]]=i;
}
int ans=0;
for(int i=0;i<n;i++){
ans=max(ans,max(first[v[i]]-i,i-last[v[i]]));
}
return ans;
}
vector<int> countScans(vector<int> _v,vector<int> _x,vector<int> _y){
swap(v,_v);
swap(x,_x);
swap(y,_y);
n=v.size(),q=x.size();
compress();
//cerr<<"v: ";for(const auto& i:v)cerr<<i<<" ";cerr<<endl;
vector<int> ans(q);
for(int i=0;i<q;i++){
v[x[i]]=y[i];
ans[i]=solve();
}
return ans;
}
