#include <bits/stdc++.h>
template <class T>
using Vec = std::vector<T>;
Vec<int> countScans(Vec<int> A, Vec<int> X, Vec<int> V) {
const int N = A.size();
const int Q = X.size();
Vec<int> big(N);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < i; ++j) {
if (A[j] > A[i]) {
big[i] += 1;
}
}
}
Vec<int> ret(Q);
for (int i = 0; i < Q; ++i) {
for (int j = X[i] + 1; j < N; ++j) {
if (A[X[i]] <= A[j] && V[i] > A[j]) {
big[j] += 1;
}
if (A[X[i]] > A[j] && V[i] <= A[j]) {
big[j] -= 1;
}
}
A[X[i]] = V[i];
big[X[i]] = 0;
for (int j = 0; j < X[i]; ++j) {
if (A[j] > A[X[i]]) {
big[X[i]] += 1;
}
}
ret[i] = *std::max_element(big.begin(), big.end());
}
return ret;
}
#ifdef __APPLE__
int main() {
int N, Q;
std::cin >> N >> Q;
Vec<int> A(N);
Vec<int> X(Q), V(Q);
for (auto &x: A) {
std::cin >> x;
}
for (int i = 0; i < Q; ++i) {
std::cin >> X[i] >> V[i];
}
for (auto x: countScans(A, X, V)) {
std::cout << x << '\n';
}
return 0;
}
#endif
