#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
vector<int>countScans(vector<int>a, vector<int>x, vector<int>v){
int n = a.size(), q = x.size();
vector<int>ans(q, 0);
if(n <= 2000 && q <= 2000){
for(int _i = 0; _i < q; _i++){
a[x[_i]] = v[_i];
vector<int>A = a;
while(true){
bool swapped = false;
for(int i = 1; i < n; i++){
if(A[i - 1] > A[i]){
swap(A[i - 1], A[i]);
swapped = true;
}
}
if(!swapped){
break;
}
ans[_i]++;
}
}
}
else if(n <= 8000 && q <= 8000){
vector<int>p(n);
iota(p.begin(), p.end(), 0);
for(int _i = 0; _i < q; _i++){
a[x[_i]] = v[_i];
sort(p.begin(), p.end(), [&] (int i, int j) -> bool{
return a[i] < a[j] || (a[i] == a[j] && i < j);
});
for(int i = 0; i < n; i++){
maximize(ans[_i], p[i] - i);
}
}
}
else if(n <= 50000 && q <= 50000 && *max_element(a.begin(), a.end()) <= 100 && *max_element(v.begin(), v.end()) <= 100){
vector<set<int>>pos(101);
for(int i = 0; i < n; i++){
pos[a[i]].insert(i);
}
for(int _i = 0; _i < q; _i++){
pos[a[x[_i]]].erase(x[_i]);
pos[a[x[_i]] = v[_i]].insert(x[_i]);
for(int i = 1, cnt = 0; i < 101; i++){
if(!pos[i].empty()){
maximize(ans[_i], *pos[i].rbegin() - (cnt += pos[i].size()) + 1);
}
}
}
}
else{
}
return ans;
}
