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