/*
doing virtual contest
start: 10:00
finish: 14:00
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
int n = (int)a.size(), q = (int)x.size();
vector<int> ret;
for (int j = 0; j < q; ++j) {
a[x[j]] = v[j];
vector<pair<int, int>> srt;
for (int i = 0; i < n; ++i) srt.push_back({a[i], i});
sort(srt.begin(), srt.end());
vector<int> p(n);
for (int i = 0; i < n; ++i) p[srt[i].second] = i;
/*for (int i = 0; i < n; ++i) cout << a[i] << " ";
cout << '\n';
for (int i = 0; i < n; ++i) cout << p[i] << " ";
cout << '\n';*/
int ans = 0;
for (int i = 0; i < n; ++i) ans = max(ans, i - p[i]);
ret.push_back(ans);
}
return ret;
}
#ifdef LOCAL
int main() {
freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> x(q), v(q);
for (int i = 0; i < q; ++i) cin >> x[i] >> v[i];
auto s = countScans(a, x, v);
for (int i = 0; i < q; ++i) cout << s[i] << '\n';
return 0;
}
#endif
