#include <bits/stdc++.h>
using namespace std;
const int ST1_LIM = 2000;
const int ST2_LIM = 8000;
const int ST3_LIM = 50000;
int n, q;
vector <int> cur;
vector <int> v;
vector <int> ans;
int bubble_sort() {
cur.resize(n);
for (int i = 0; i < n; i++) {
cur[i] = v[i];
}
int num_swaps = 0;
while (true) {
bool saw_new_swap = false;
for (int i = 0; i < n - 1; i++) {
if (cur[i] > cur[i + 1]) {
saw_new_swap = true;
swap(cur[i], cur[i + 1]);
}
}
if (saw_new_swap) {
num_swaps++;
} else {
break;
}
}
return num_swaps;
}
vector<int> solve_st1(vector<int> A, vector<int> X, vector<int> V) {
for (int i = 0; i < q; i++) {
v[X[i]] = V[i];
ans.push_back(bubble_sort());
}
return ans;
}
vector<int> solve_st2(vector<int> A, vector<int> X, vector<int> V) {
return ans;
}
vector<int> solve_st3(vector<int> A, vector<int> X, vector<int> V) {
return ans;
}
vector<int> solve_st4(vector<int> A, vector<int> X, vector<int> V) {
return ans;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
n = (int) A.size();
q = (int) X.size();
v.resize(n);
for (int i = 0; i < n; i++) {
v[i] = A[i];
}
if (max(n, q) <= ST1_LIM) {
return solve_st1(A, X, V);
} else if (max(n, q) <= ST2_LIM) {
return solve_st2(A, X, V);
} else if (max(n, q) <= ST3_LIM) {
return solve_st3(A, X, V);
} else {
return solve_st4(A, X, V);
}
}
/* int main() {
vector<int> A;
vector<int> X;
vector<int> V;
int _n, _q;
cin >> _n >> _q;
A.resize(_n);
X.resize(_q);
V.resize(_q);
for (int i = 0; i < _n; i++) {
cin >> A[i];
}
for (int i = 0; i < _q; i++) {
cin >> X[i] >> V[i];
}
vector<int> S = countScans(A, X, V);
for (int i = 0; i < _q; i++) {
cout << S[i] << "\n";
}
return 0;
} */
