#include <bits/stdc++.h>
#define N 100005
#define B 300
#define pb push_back
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
using namespace std;

template <typename T>
inline void read(T &num) {
	T x = 0, ff = 1; char ch = getchar();
	for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') ff = -1;
	for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x<<3)+(x<<1)+(ch^'0');
	num = x * ff;
}
template <typename T>
void write(T num) {
	if (num >= 10) write(num/10);
	putchar(num%10+'0'); 
}

int n, Q, a[N];
int X[N*3], H[N*3], srt[N*4];
int q[N], q2[N], bel[N], mdf[N];
int val[N], ql[N], qr[N], cnt;
int head[N], pre[N<<1], to[N<<1], sz; 
int fa[N], siz[N], son[N], dfn[N], rnk[N], top[N], tme;
int P[N], pc, pmx[N], smx[N], aa[N], pl[N], pr[N];
set<int> st[N*4]; 

inline void adeg(int u, int v) {
	pre[++sz] = head[u]; head[u] = sz; to[sz] = v; 
}

void dfs1(int x) {
	siz[x] = 1; son[x] = 0;
	for (int i = head[x]; i; i = pre[i]) {
		int y = to[i];
		fa[y] = x; dfs1(y); siz[x] += siz[y];
		if (!son[x] || siz[son[x]] < siz[y]) son[x] = y;
	}
}
void dfs2(int x, int tp) {
	top[x] = tp; rnk[dfn[x]=++tme] = x;
	if (son[x]) dfs2(son[x], tp);
	for (int i = head[x]; i; i = pre[i]) if (to[i] != son[x]) dfs2(to[i], to[i]);
}

struct segtree {
	int mn[N<<2], tg[N<<2], cc[N<<2];
	void build(int p, int l, int r) {
		mn[p] = tg[p] = 0; cc[p] = r-l+1;
		if (l == r) return;
		int mid = (l+r)>>1;
		build(p<<1,l,mid); build(p<<1|1,mid+1,r);
	}
	inline void pushtg(int p, int v) { mn[p]+=v;tg[p]+=v; }
	inline void pushdw(int p) {
		if (!tg[p]) return;
		pushtg(p<<1,tg[p]); pushtg(p<<1|1,tg[p]);
		tg[p] = 0;
	}
	inline void pushup(int p) {
		mn[p] = min(mn[p<<1],mn[p<<1|1]);
		cc[p] = (mn[p<<1]==mn[p])*cc[p<<1] + (mn[p<<1|1]==mn[p])*cc[p<<1|1];
	}
	void upd(int p, int l, int r, int x, int y, int v) {
		if (x <= l && r <= y) return pushtg(p,v);
		pushdw(p); int mid = (l+r)>>1;
		if (x <= mid) upd(p<<1,l,mid,x,y,v);
		if (mid < y) upd(p<<1|1,mid+1,r,x,y,v);
		pushup(p);
	}
} T;

void UPD(int x, int v, int add) {
	while (x) {
		if (fa[top[x]] && val[fa[top[x]]] <= v) {
			T.upd(1,1,cnt,dfn[top[x]],dfn[x],add);
			x = fa[top[x]];
		} else {
			int l = dfn[top[x]], r = dfn[x], mid = 0, ok = 0;
			while (l <= r) {
				mid = (l+r)>>1;
				if (val[rnk[mid]] <= v) r = (ok=mid)-1;
				else l = mid+1;
			}
			if (ok) T.upd(1,1,cnt,ok,dfn[x],add); 
			break;
		}
	}
}

void initTree() {
	for (int i = 1; i <= n; i++) bel[i] = 1;
	cnt = 1; sz = 0; int top = 0, t2 = 0; 
	for (int i = 1; i <= n; i++) if (!mdf[i]) {
		while (top && a[q[top]] < a[i]) --top;
		if (top && a[q[top]] == a[i]) {
			int l = q[top], r = i; 
			++cnt; val[cnt] = a[i]; ql[cnt] = l; qr[cnt] = r;
			head[cnt] = 0;
			while (t2 && ql[q2[t2]] > l) {
				while (r > qr[q2[t2]]) bel[r--] = cnt;
				r = ql[q2[t2]]-1; 
				adeg(cnt, q2[t2--]);
			}
			while (r >= l) bel[r--] = cnt;
			q2[++t2] = cnt; 
		}
		q[++top] = i;
	}
	head[1] = 0; val[1] = 1e9+7;
	while (t2) adeg(1, q2[t2--]);
	
	dfs1(1); tme = 0; dfs2(1, 1);
	T.build(1, 1, cnt);
	
	for (int i = 1; i <= pc; i++) {
		int x = P[i];
		mdf[x] = bel[x]; 
		UPD(mdf[x], a[x], 1);
	}
}

void getLR(int x) {
	pl[x] = pr[x] = 0;
	auto it = st[a[x]].find(x);
	if (it != st[a[x]].begin()) pl[x] = *prev(it);
	if (next(it) != st[a[x]].end()) pr[x] = *next(it);
}
void init1000Q() {
	P[pc+1] = n+1;
	for (int i = 0; i <= pc; i++) {
		pmx[P[i]] = 0;
		for (int j = P[i]+1; j < P[i+1]; j++) pmx[j] = max(pmx[j-1],a[j]);
		smx[P[i+1]] = 0;
		for (int j = P[i+1]-1; j > P[i]; j--) smx[j] = max(smx[j+1],a[j]);
		aa[P[i+1]-1] = pmx[P[i+1]-1];
		aa[P[i]+1] = smx[P[i]+1];
	}
	for (int i = 1; i <= pc; i++) getLR(P[i]);
}
int calc() {
	for (int i = 1; i <= pc; i++) aa[P[i]] = a[P[i]];
	int top = 0, ret = 0;
	for (int i = 1; i <= pc; i++) {
		if (P[i-1]+1 <= P[i]-1) {
			int x = P[i-1]+1;			
			while (top && aa[q[top]] < aa[x]) --top;
			q[++top] = x;
		}
		int x = P[i];
		while (top && aa[q[top]] < aa[x]) --top;
		if (top && mdf[q[top]] && pl[x] == q[top]) ++ret;
		if (pl[x] && !mdf[pl[x]]) 
			if ((!top||q[top]<=pl[x]) && smx[pl[x]+1] < a[x]) ++ret;
		q[++top] = x;
	}
	top = 0;
	for (int i = pc; i; i--) {
		if (P[i]+1 <= P[i+1]-1) {
			int x = P[i+1]-1;
			while (top && aa[q[top]] < aa[x]) --top;
			q[++top] = x;		
		}
		int x = P[i];
		while (top && aa[q[top]] < aa[x]) --top;
		if (pr[x] && !mdf[pr[x]]) 
			if ((!top||q[top]>=pr[x]) && pmx[pr[x]-1] < a[x]) ++ret;
		q[++top] = x;
	}
	return ret;
}

void work(int L, int R) {
	memset(mdf, 0, sizeof(mdf));
	for (int i = L; i <= R; i++) mdf[X[i]] = 1;
	pc = 0; for (int i = 1; i <= n; i++) if (mdf[i]) P[++pc] = i;
	initTree();
	init1000Q();
	if (L == 1) write((T.cc[1]-1)+calc()), putchar('\n');
	for (int i = L; i <= R; i++) {
		int x = X[i];
		UPD(mdf[x], a[x], -1);
		auto it = st[a[x]].find(x);
		int pre = it==st[a[x]].begin()?0:*prev(it);
		int nxt = next(it)==st[a[x]].end()?0:*next(it);
		if (pre && mdf[pre]) pr[pre] = nxt;
		if (nxt && mdf[nxt]) pl[nxt] = pre;
		st[a[x]].erase(x);
		
		a[x] = H[i];
		
		UPD(mdf[x], a[x], 1);
		it = st[a[x]].insert(x).first;
		pre = it==st[a[x]].begin()?0:*prev(it);
		nxt = next(it)==st[a[x]].end()?0:*next(it);
		if (pre && mdf[pre]) pr[pre] = x;
		if (nxt && mdf[nxt]) pl[nxt] = x;
		pl[x] = pre; pr[x] = nxt;
		
		write((T.cc[1]-1)+calc()), putchar('\n');
	}
}

int main() {
//	freopen("ex_data3.in", "r", stdin); freopen("my.out", "w", stdout);
//	freopen("overlook.in", "r", stdin); freopen("overlook.out", "w", stdout);
	read(n); read(Q); int mx = 0;
	for (int i = 1; i <= n; i++) {
		read(a[i]); srt[++mx] = a[i];
	}
	for (int i = 1; i <= Q; i++) {
		read(X[i]); read(H[i]);
		srt[++mx] = H[i];
	}
	sort(srt+1,srt+mx+1); mx = unique(srt+1,srt+mx+1)-srt-1;
	auto fnd = [&](int x) { return lower_bound(srt+1,srt+mx+1,x)-srt; };
	for (int i = 1; i <= n; i++) {
		a[i] = fnd(a[i]); st[a[i]].insert(i);
	}
	for (int i = 1; i <= Q; i++) H[i] = fnd(H[i]);
	for (int i = 1; i <= Q; i+=B) {
		work(i,min(Q,i+B-1));
	}
	return 0;
}