#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; static 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; }