#include "bubblesort2.h"
#include <iostream>
#include <iterator>
#include <set>
using namespace std;
set<int> S;
int Vec[500010];
int Maxi[500010];
int Solve(int a){
int ans=0;
for(int i=0;i<a;i++){
if(Vec[i]>Vec[a]) ans++;
}
return ans;
}
vector<int> count_scans(vector<int> A,vector<int> X,vector<int> V){
int Q=X.size();
int n=A.size();
vector<int> Answer;
for(int i=0;i<n;i++){
Vec[i]=A[i];
Maxi[i]=Solve(i);
}
for(int i=0;i<Q;i++){
int Nuevo=V[i];
int Pos=X[i];
int Antiguo=Vec[Pos];
Vec[Pos]=Nuevo;
Maxi[Pos]=Solve(Pos);
for(int j=Pos+1;j<n;j++){
int b=Vec[j];
if(Antiguo>=b and Nuevo<b) Maxi[j]--;
if(Antiguo<=b and Nuevo>b) Maxi[j]++;
}
int MAXIMO=0;
for(int i=0;i<n;i++){
MAXIMO=max(MAXIMO,Maxi[i]);
}
Answer.push_back(MAXIMO);
}
return Answer;
}
I2luY2x1ZGUgImJ1YmJsZXNvcnQyLmgiCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGl0ZXJhdG9yPgojaW5jbHVkZSA8c2V0Pgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpzZXQ8aW50PiBTOwppbnQgVmVjWzUwMDAxMF07CmludCBNYXhpWzUwMDAxMF07CgoKaW50IFNvbHZlKGludCBhKXsKCWludCBhbnM9MDsKCWZvcihpbnQgaT0wO2k8YTtpKyspewoJCWlmKFZlY1tpXT5WZWNbYV0pIGFucysrOwoJfQoJcmV0dXJuIGFuczsKfQoKdmVjdG9yPGludD4gY291bnRfc2NhbnModmVjdG9yPGludD4gQSx2ZWN0b3I8aW50PiBYLHZlY3RvcjxpbnQ+IFYpewoJaW50IFE9WC5zaXplKCk7CglpbnQgbj1BLnNpemUoKTsKCXZlY3RvcjxpbnQ+IEFuc3dlcjsKCWZvcihpbnQgaT0wO2k8bjtpKyspewoJCVZlY1tpXT1BW2ldOwoJCU1heGlbaV09U29sdmUoaSk7Cgl9Cglmb3IoaW50IGk9MDtpPFE7aSsrKXsKCQlpbnQgTnVldm89VltpXTsKCQlpbnQgUG9zPVhbaV07CgkJaW50IEFudGlndW89VmVjW1Bvc107CgkJVmVjW1Bvc109TnVldm87CgkJTWF4aVtQb3NdPVNvbHZlKFBvcyk7CgkJZm9yKGludCBqPVBvcysxO2o8bjtqKyspewoJCQlpbnQgYj1WZWNbal07CgkJCWlmKEFudGlndW8+PWIgYW5kIE51ZXZvPGIpIE1heGlbal0tLTsKCQkJaWYoQW50aWd1bzw9YiBhbmQgTnVldm8+YikgTWF4aVtqXSsrOwoJCX0KCQlpbnQgTUFYSU1PPTA7CgkJZm9yKGludCBpPTA7aTxuO2krKyl7CgkJCU1BWElNTz1tYXgoTUFYSU1PLE1heGlbaV0pOwoJCX0KCQlBbnN3ZXIucHVzaF9iYWNrKE1BWElNTyk7Cgl9CglyZXR1cm4gQW5zd2VyOwp9Cg==