#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
const int MAX_N = 2000;
vector<int> a, poz;
int smen[MAX_N+1];
bool cmp(int x, int y) {
return a[x] < a[y] || (a[x] == a[y] && x < y);
}
int getInv(int n) {
int right = -1;
sort(poz.begin(), poz.end(), cmp);
for(int i = 0; i <= n; ++i)
smen[i] = 0;
for(int i = 0; i < n; ++i) {
right = max(right, poz[i]);
if(right > poz[i]) {
smen[poz[i]]++;
smen[right]--;
}
}
int p = 0;
int rez = 0;
for(int i = 0; i < n; ++i) {
p += smen[i];
rez = max(rez, p);
}
return rez;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int n, q;
a = A;
q = X.size();
std::vector<int> rez(q);
n = A.size();
for(int i = 0; i < n; ++i)
poz.push_back(i);
for(int i = 0; i < q; ++i) {
a[X[i]] = V[i];
rez[i] = getInv(n);
}
return rez;
}
