#include <bits/stdc++.h>
template <class T>
using Vec = std::vector<T>;
struct Fenwick {
Vec<int> data;
Fenwick(int n): data(n + 1) { }
void add(int i, int x) {
i += 1;
while (i < (int) data.size()) {
data[i] += x;
i += (i & -i);
}
}
int get(int i) {
int ret = 0;
while (i > 0) {
ret += data[i];
i -= (i & -i);
}
return ret;
}
};
struct Mn {
int value;
static Mn id() {
return Mn { -1000000000 };
}
Mn operator + (const Mn other) const {
return Mn { std::max(value, other.value) };
}
};
struct Ef {
int add;
static Ef id() {
return Ef { 0 };
}
Ef operator + (const Ef other) const {
return Ef { add + other.add };
}
};
Mn operator + (const Mn mn, const Ef ef) {
return Mn { mn.value + ef.add };
}
struct Segtree {
struct Node {
Mn mn;
Ef ef;
};
void fetch(const int i) {
data[i].mn = data[i * 2 + 0].mn + data[i * 2 + 1].mn;
}
void apply(const int i, const Ef ef) {
data[i].mn = data[i].mn + ef;
data[i].ef = data[i].ef + ef;
}
void flush(const int i) {
apply(i * 2 + 0, data[i].ef);
apply(i * 2 + 1, data[i].ef);
}
static int ctzr(const int i) {
return __builtin_ctzll(i);
}
static int height(const int i) {
return 64 - __builtin_clzll(i);
}
void pushdown(const int i) {
const auto lsb = ctzr(i);
for (int d = height(i); --d > lsb;) {
flush(i >> d);
}
}
void pullup(int i) {
i >>= ctzr(i);
while (i != 1) {
i >>= 1;
fetch(i);
}
}
Vec<Node> data;
Segtree(const Vec<int> &vec) {
const auto size = vec.size();
data.resize(size * 2, Node { Mn::id(), Ef::id() });
for (int i = 0; i < size; ++i) {
data[size + i].mn.value = vec[i];
}
for (int i = size - 1; i > 0; --i) {
fetch(i);
}
}
void operate(int l, int r, const int x) {
l += size();
r += size();
pushdown(l);
pushdown(r);
const auto cl = l;
const auto cr = r;
const auto ef = Ef { x };
while (l < r) {
if (l & 1) {
apply(l, ef);
l += 1;
}
if (r & 1) {
r -= 1;
apply(r, ef);
}
l >>= 1;
r >>= 1;
}
pullup(cl);
pullup(cr);
}
int fold(int l, int r) {
l += size();
r += size();
pushdown(l);
pushdown(r);
Mn mn = Mn::id();
while (l < r) {
if (l & 1) {
mn = mn + data[l].mn;
l += 1;
}
if (r & 1) {
r -= 1;
mn = mn + data[r].mn;
}
l >>= 1;
r >>= 1;
}
return mn.value;
}
int assign(int i, int x) {
i += size();
pushdown(i);
pushdown(i + 1);
data[i].mn = Mn { x };
data[i].ef = Ef::id();
while (i > 1) {
i >>= 1;
fetch(i);
}
}
int size() const {
return data.size() / 2;
}
};
Vec<int> countScans(Vec<int> A, Vec<int> X, Vec<int> V) {
const int N = A.size();
const int Q = X.size();
if (N <= 8000 && Q <= 8000) {
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;
}
else {
for (auto &x: A) {
x -= 1;
if (x >= 100) {
return { };
}
}
for (auto &x: V) {
x -= 1;
if (x >= 100) {
return { };
}
}
Vec<Fenwick> fen(100, Fenwick(N));
Vec<Segtree> seg(100, Segtree(Vec<int>(N, -1000000000)));
for (int i = 0; i < N; ++i) {
fen[A[i]].add(i, 1);
int sum = 0;
for (int j = V[i] + 1; j < 100; ++j) {
sum += fen[j].get(i);
}
seg[A[i]].assign(i, sum);
}
Vec<int> ret(Q);
for (int i = 0; i < Q; ++i) {
int sum = 0;
for (int j = V[i] + 1; j < 100; ++j) {
sum += fen[j].get(X[i]);
}
fen[A[X[i]]].add(X[i], -1);
seg[A[X[i]]].assign(X[i], -1000000000);
fen[V[i]].add(X[i], 1);
seg[V[i]].assign(X[i], sum);
if (A[X[i]] < X[i]) {
for (int j = A[X[i]]; j < V[j]; ++j) {
seg[j].operate(X[i] + 1, N, 1);
}
}
else {
for (int j = V[i]; j < A[X[i]]; ++j) {
seg[j].operate(X[i] + 1, N, -1);
}
}
A[X[i]] = V[i];
for (int j = 0; j < 100; ++j) {
ret[i] = std::max(ret[i], seg[j].fold(0, N));
}
}
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
