#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int a[500100];
int dp[500100];
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
int t = X.size();
int n = A.size();
for(int i=1; i<=n; i++){
a[i] = A[i-1];
}
for(int i=1; i<=n; i++){
dp[i] = 0;
for(int j=1; j<=i; j++){
dp[i] += (a[i] < a[j]);
}
}
vector<int> res;
for(int j=0; j<t; j++){
int pos = X[j] + 1;
int x = V[j];
for(int i=pos+1; i<=n; i++){
dp[i] -= (a[i] < a[pos]);
}
a[pos] = x;
for(int i=pos+1; i<=n; i++){
dp[i] += (a[i] < a[pos]);
}
dp[pos] = 0;
for(int i=1; i<=pos; i++){
dp[pos] += (a[i] > a[pos]);
}
int mx = 0;
// for(int i=1; i<=n; i++) cout<<a[i]<<'\n';
for(int i=1; i<=n; i++) mx = max(mx, dp[i]);
res.pb(mx);
}
return res;
}
