#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 01;
vector<ii> rrh;
int f[N], T[N << 2], lazy[N << 2];
void push(int s, int l, int r) {
if (!lazy[s]) return;
T[s] += lazy[s];
if (l != r) {
lazy[s << 1] += lazy[s];
lazy[s << 1 | 1] += lazy[s];
}
lazy[s] = 0;
}
void up(int s, int l, int r, int from, int to, int val) {
push(s, l, r);
if (l > to || r < from) return;
if (from <= l && r <= to) {
lazy[s] += val;
push(s, l, r);
return;
}
int mid = l + r >> 1;
up(s << 1, l, mid, from, to, val);
up(s << 1 | 1, mid + 1, r, from, to, val);
T[s] = max(T[s << 1], T[s << 1 | 1]);
}
int id(int pos, int val) {
return upper_bound(rrh.begin(), rrh.end(), make_pair(val, pos)) - rrh.begin();
}
vector<int> countScans(vector<int> a, vector<int> pos, vector<int> val) {
vector<int> ans(pos.size());
int n = a.size();
for(int i = 0; i < n; i++) rrh.emplace_back(a[i], i);
for(int i = 0; i < pos.size(); i++) rrh.emplace_back(val[i], pos[i]);
sort(rrh.begin(), rrh.end());
rrh.resize(unique(rrh.begin(), rrh.end()) - rrh.begin());
int m = rrh.size();
for(int i = 0; i < n; i++) {
int p = id(i, a[i]);
up(1, 1, m, p, p, i + 1);
up(1, 1, m, p, m, -1);
}
for(int i = 0; i < pos.size(); i++) {
int p = id(pos[i], a[pos[i]]);
up(1, 1, m, p, p, -pos[i] - 1);
up(1, 1, m, p, m, 1);
a[pos[i]] = val[i];
p = id(pos[i], val[i]);
up(1, 1, m, p, p, pos[i] + 1);
up(1, 1, m, p, m, -1);
ans[i] = T[1];
}
return ans;
}
#ifdef ngu
int main() {
freopen ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
int n, q; cin >> n >> q;
vector<int> a(n), x(q), v(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> ret = countScans(a, x, v);
for(int &j : ret) cout << j << endl;
}
#endif // ngu
