#include "bubblesort2.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define dbg(x) cerr << #x << ": " << x << endl;
struct FenwickTree {
vector<int> tree;
int size;
FenwickTree(int n) {
size = n;
tree.resize(size);
}
void update(int pos, int value) {
for (int i = pos; i < size; i |= i + 1) {
tree[i] += value;
}
}
int query(int l, int r) {
int res = 0;
for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
res += tree[i];
}
for (int i = l - 1; i >= 0; i = (i & (i + 1)) - 1) {
res -= tree[i];
}
return res;
}
};
vector<int> countScans(vector<int> a, vector<int> pos, vector<int> value){
int q = pos.size();
vector<int> all_values = a;
all_values.insert(all_values.end(), value.begin(), value.end());
sort(all_values.begin(), all_values.end());
all_values.resize(unique(all_values.begin(), all_values.end()) - all_values.begin());
int k = all_values.size();
map<int, int> mp;
for (int i = 0; i < k; ++i) {
mp[all_values[i]] = i;
}
for (auto& x : a) {
x = mp[x];
}
for (auto& x : value) {
x = mp[x];
}
auto count = [&]() -> int {
// the answer is maximum number of inversions for a single number
FenwickTree tree(k);
// maybe will be better to reverse the array for simplicity
int res = 0;
for (auto x : a) {
res = max(res, tree.query(x + 1, k - 1));
tree.update(x, 1);
}
return res;
};
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
a[pos[i]] = value[i];
ans[i] = count();
}
return ans;
}
// int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// int n, q;
// cin >> n >> q;
// vector<int> a(n);
// for (auto& x : a) {
// cin >> x;
// }
// vector<int> pos(q), value(q);
// for (int i = 0; i < q; ++i) {
// cin >> pos[i] >> value[i];
// }
// for (auto x : countScans(a, pos, value)) {
// cout << x << '\n';
// }
// return 0;
// }
/*
4 2
1 2 3 4
0 3
2 1
*/
