#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int N = 1 << 18, INF = 0x3f3f3f3f;
int n, q, a[N], b[N], c[N], ans[N];
struct Wire {	// compressed tree of electric wire (lef, rig) 
	int lef, rig, val, cnt;
	Wire(int _1 = 0, int _2 = 0, int _3 = 0, int _4 = 0):
		lef(_1), rig(_2), val(_3), cnt(_4){}
} wre[19][N], _wre[N];
struct Node {	// compressed sequence
	int lef, rig; bool spe;
	Node(int _1 = 0, int _2 = 0, bool _3 = 0):
		lef(_1), rig(_2), spe(_3){}
} nod[19][N];
namespace SegT {	// magical Segment Tree
	const int M = 1 << 17;
	int mx[M<<1];
	void upd(int p, int v){
//		printf("upd(%d, %d)\n", p, v);
		for(mx[p += M] = v, p >>= 1;p;p >>= 1)
			mx[p] = max(mx[p<<1], mx[p<<1|1]);
	}
	int qryL(int p, int v){
		for(p += M-1;(p & p-1) && mx[p] < v;p = p-1>>1);
		if(mx[p] < v) return 0;
		for(;p < M;p <<= 1, p |= mx[p|1] >= v);
		return mx[p] == v ? p-M : 0;
	}
	int qryR(int p, int v){
//		printf("qryR(%d, %d)\n", p, v);
		for(p += M+1;(p & p+1) && mx[p] < v;p = p+1>>1);
		if(mx[p] < v) return 0;
		for(;p < M;p <<= 1, p |= mx[p] < v);
		return mx[p] == v ? p-M : 0;
	}
}
int rev[N];	// correspond index of the compressed sequence
int _b[19][N];	// temporary backup of array `b`
bool flg[N];	// is a key point in the virtual tree
bool vis[N];
int buc[N], pos[N], qwa[N], nsta[19][N], _nsta[19][N], tp;
int stk[N];	// index of monotonic stack
void krow(int dep, int nods, int &wres){
	memcpy(nod[dep+1], nod[dep], (sizeof(Node)) * (nods + 1));
	for(int i = 1;i <= nods;++ i)
		if(nsta[dep][i]) nod[dep+1][i].spe = false;
	static Wire hl[N], hr[N], buk[N];
	int hls = 0;
	auto useful = [&](int p){
		if(!p) return 0;
		int l = 1, r = nods, md;
		while(l <= r){
			md = l + r >> 1;
			if(p < nod[dep][md].lef) r = md - 1;
			else if(p > nod[dep][md].rig) l = md + 1;
			else return md;
		} return 0;
	};
	memset(vis, 0, nods + 1);
	memset(buc, 0, nods + 2 << 2);
	for(int i = 1;i <= nods;++ i) if(nsta[dep][i]){
		int lef = useful(SegT::qryL(nod[dep][i].lef, nsta[dep][i]));
		if(lef){
			if(nsta[dep][lef]){
				vis[lef] = true;
				hr[lef] = Wire(lef, i, nsta[dep][i], 1);
			} else hl[++hls] = Wire(lef, i, nsta[dep][i], 1);
		}
	}
	for(int i = 1;i <= nods;++ i) if(nsta[dep][i] && !vis[i]){
		int rig = useful(SegT::qryR(nod[dep][i].lef, nsta[dep][i]));
		if(rig){hr[i] = Wire(i, rig, nsta[dep][i], 1); vis[i] = true;}
	}
	for(int i = 1;i <= hls;++ i) ++buc[hl[i].lef+1];
	for(int i = 1;i <= nods;++ i) buc[i+1] += buc[i];
	for(int i = 1;i <= hls;++ i) buk[++buc[hl[i].lef]] = hl[i];
	memcpy(hl, buk, (sizeof(Wire)) * (hls + 1));
	memset(flg, 0, wres + 1); tp = 0;
	for(int i = 1, j = 1;i <= nods;++ i){
		for(;tp && wre[dep][stk[tp]].rig == i;-- tp);
		for(;j <= wres && wre[dep][j].lef == i;++ j)
			stk[++tp] = j;
		for(;tp && wre[dep][stk[tp]].val <= nsta[dep][i];-- tp)
			flg[stk[tp]] = true;
	}
	int ps[3] = {1, 1, 1}, nwres = 0;
	while(true){
		while(ps[1] <= nods && !vis[ps[1]]) ++ ps[1];
		while(ps[2] <= wres && flg[ps[2]]) ++ ps[2];
		if(ps[0] > hls && ps[1] > nods && ps[2] > wres)
			break;
		pii pv0 = ps[0] <= hls ? MP(hl[ps[0]].lef, -hl[ps[0]].rig) : MP(INF, INF),
			pv1 = ps[1] <= nods ? MP(hr[ps[1]].lef, -hr[ps[1]].rig) : MP(INF, INF),
			pv2 = ps[2] <= wres ? MP(wre[dep][ps[2]].lef, -wre[dep][ps[2]].rig) : MP(INF, INF),
			pv_ = min(pv0, min(pv1, pv2));
		if(pv0 == pv_) wre[dep+1][++nwres] = hl[ps[0]++];
		else if(pv1 == pv_) wre[dep+1][++nwres] = hr[ps[1]++];
		else wre[dep+1][++nwres] = wre[dep][ps[2]++];
	}
	wres = nwres;
}
struct PathV {	// vertex of path from root when dfs on the tree
	int id, rig, val;
	PathV(int _1 = 0, int _2 = 0, int _3 = 0):
		id(_1), rig(_2), val(_3){}
} pat[N];
void work(int dep, int ql, int qr, int nods, int wres, int nans){
//	printf("ql = %d, qr = %d, nods = %d, wres = %d\n", ql, qr, nods, wres);
//	for(int i = 1;i <= wres;++ i)
//		printf("wre[%d] = %d, %d, %d, %d\n", i, wre[dep][i].lef, wre[dep][i].rig, wre[dep][i].val, wre[dep][i].cnt);
	if(ql == qr){
//		printf("b[%d] = %d, c[%d] = %d\n", ql, b[ql], ql, c[ql]);
		if(SegT::qryL(nod[dep][b[ql]].lef, c[ql])) ++ nans;
//		printf("nans = %d\n", nans);
		if(SegT::qryR(nod[dep][b[ql]].lef, c[ql])) ++ nans;
//		printf("nans = %d\n", nans);
		for(int i = 0;i < wres;++ i)
			if(wre[dep][i].rig < b[ql] || wre[dep][i].lef > b[ql] || wre[dep][i].val > c[ql])
				nans += wre[dep][i].cnt;
		ans[ql] = nans; return;
	}
	int md = ql + qr >> 1, _ = 0;
	for(int i = 1;i <= nods;++ i){
		if(_ && !nod[dep][i].spe && !nod[dep][_].spe)
			nod[dep][_].rig = nod[dep][i].rig;
		else
			nod[dep][++_] = nod[dep][i];
		rev[i] = _;
	}
	nods = _; _ = 0;
//	for(int i = 1;i <= nods;++ i)
//		printf("nod[%d] = %d, %d, %d\n", i, nod[dep][i].lef, nod[dep][i].rig, nod[dep][i].spe);
	memcpy(_b[dep] + ql, b + ql, qr - ql + 1 << 2);
	for(int i = ql;i <= qr;++ i) b[i] = rev[b[i]];
	for(int i = 1;i <= wres;++ i){
		wre[dep][i].lef = rev[wre[dep][i].lef];
		wre[dep][i].rig = rev[wre[dep][i].rig];
		if(wre[dep][i].lef == wre[dep][i].rig)
			nans += wre[dep][i].cnt;
		else
			wre[dep][++_] = wre[dep][i];
	}
	wres = _; _ = 0;
	memset(buc, 0, nods + 2 << 2);
	memset(flg, 0, wres + 1);
	for(int i = ql;i <= qr;++ i) ++ buc[b[i]+1];
	for(int i = 1;i <= nods;++ i) buc[i+1] += buc[i];
	for(int i = ql;i <= qr;++ i) qwa[++buc[b[i]]] = c[i];
	tp = 0;
	auto useful = [&](int val){
		if(val < pat[tp].val) return 0;
		int L = 1, R = tp, md;
		while(L < R) pat[md = L+R>>1].val <= val ? R = md : L = md+1;
		return pat[L].id;
	};
	for(int i = 1, j = 1;i <= nods;++ i){
		for(;tp && pat[tp].rig <= i;-- tp);
		for(;j <= wres && wre[dep][j].rig <= i;++ j)
			pat[++tp] = PathV(j, wre[dep][j].rig, wre[dep][j].val);
		if(nod[dep][i].spe) flg[useful(a[nod[dep][i].lef])] = true;
		for(int k = buc[i-1]+1;k <= buc[i];++ k)
			flg[useful(qwa[k])] = true;
	}
	_wre[_ = 1] = wre[dep][1];
	for(int i = 2;i <= wres;++ i)
		if(!flg[i] && wre[dep][i].lef == _wre[_].lef && wre[dep][i].rig == _wre[_].rig)
			_wre[_].cnt += wre[dep][i].cnt;
		else
			_wre[++_] = wre[dep][i];
	memcpy(wre[dep], _wre, (sizeof(Wire)) * (_ + 1)); wres = _;
	memset(nsta[dep], 0, nods + 1 << 2);
	for(int i = 1;i <= nods;++ i)
		if(nod[dep][i].spe) nsta[dep][i] = a[nod[dep][i].lef];
	for(int i = ql;i <= md;++ i) nsta[dep][b[i]] = 0;
	for(int i = 1;i <= nods;++ i)
		if(nsta[dep][i]) SegT::upd(nod[dep][i].lef, nsta[dep][i]);
	krow(dep, nods, _ = wres);
	work(dep + 1, ql, md, nods, _, nans);
	// ------------------------------
	for(int i = 1;i <= nods;++ i)
		if(nsta[dep][i]) SegT::upd(nod[dep][i].lef, 0);
	memset(nsta[dep], 0, nods + 1 << 2);
	for(int i = ql;i <= md;++ i)
		nsta[dep][b[i]] = c[i];
	for(int i = 1;i <= nods;++ i) if(nod[dep][i].spe){
		_nsta[dep][i] = a[nod[dep][i].lef];
		if(nsta[dep][i]) a[nod[dep][i].lef] = nsta[dep][i];
	}
	for(int i = md+1;i <= qr;++ i) nsta[dep][b[i]] = 0;
	for(int i = 1;i <= nods;++ i)
		if(nsta[dep][i]) SegT::upd(nod[dep][i].lef, nsta[dep][i]);
	krow(dep, nods, _ = wres);
	work(dep + 1, md+1, qr, nods, _, nans);
	// -------------------------------
	for(int i = 1;i <= nods;++ i) if(nod[dep][i].spe){
		a[nod[dep][i].lef] = _nsta[dep][i];
		if(nsta[dep][i]) SegT::upd(nod[dep][i].lef, 0);
	}
	memcpy(b + ql, _b[dep] + ql, qr - ql + 1 << 2);
}
bitset<N> nst;	// non-static
int main(){
//	freopen("a.in", "r", stdin);
	ios::sync_with_stdio(false);
	cin >> n >> q; //n += 2;
	for(int i = 1;i <= n;++ i) cin >> a[i];
	for(int i = 1;i <= q;++ i) cin >> b[i] >> c[i];
	int wres = 0;
	for(int i = 1;i <= q;++ i) nst.set(b[i]);
	for(int i = 1;i <= n;++ i) if(!nst.test(i)){
		for(;tp && a[stk[tp]] < a[i];-- tp);
		if(tp && a[stk[tp]] == a[i]){
			wre[0][++wres] = Wire(stk[tp], i, a[i], 1);
			-- tp;
		}
		stk[++tp] = i;
		SegT::upd(i, a[i]);
	}
	for(int i = 1;i <= n;++ i) nod[0][i] = Node(i, i, nst.test(i));
	tp = 0;
	for(int i = 1;i <= n;++ i){
		for(;tp && a[stk[tp]] < a[i];-- tp);
		if(tp && a[stk[tp]] == a[i]){
			++ ans[0]; -- tp;
		}
		stk[++tp] = i;
	}
	work(0, 1, q, n, wres, 0);
	for(int i = 0;i <= q;++ i)
		printf("%d\n", ans[i]);
}