分析
可以发现一个性质，即连通块一定是连续的一段。证明可以设 $i<k<j$，然后讨论各种情况，并证明无论如何 $k$ 与 $i,j$ 都连通。证起来有些复杂所以此处略去（
那么我们可以枚举连通块的最右边的点 $p$，如果 $[1,p]$ 与 $[p+1,n]$ 间没有连边即 $\min_{1\leq i\leq p}a_i>\max_{p+1\leq i\leq n}a_i$ 则 $p$ 满足条件。
考虑枚举 $\max_{p+1\leq i\leq n}$，设为 $w$。将序列中 $>w$ 的数设为 $1$，$\leq w$ 的数设为 $0$，则 $p$ 满足条件当且仅当这个 $0/1$ 序列形式如同
$$
\underbrace{11\cdots 11}_{p\text{个}1}00\cdots 00
$$
因而没有必要枚举 $p$，只需要枚举 $w$ 即可，因为确定一个满足条件的 $w$ 时 $p$ 的值可以唯一确定。
所以我们只需要统计有多少个 $w$ 对应的 $0/1$ 序列是这个形式即可。
为了方便，设 $a_{0}=+\infty,a_{n+1}=0$，此时一个 $0/1$ 序列是这个形式当且仅当只有一对相邻的 $0$、$1$。于是我们对于每个 $w$ 计算相邻的 $0$、$1$ 对数即可。
考虑用线段树解决这个问题。对于相邻的两个数 $a_i,a_{i+1}$，当 $w\in[\min\{a_i,a_{i+1}\},\max\{a_i,a_{i+1}\})$ 时这两个数会构成一对 $0$、$1$，在线段树上将这个区间加 $1$ 即可。统计答案时我们需要算有多少个位置的值是 $1$，难以维护；注意到一定有一对 $0$、$1$（因为 $a_0=+\infty,a_{n+1}=0$），所以我们只要维护最小值个数即可。另外注意统计答案时不能将不在序列中的数算进去。
代码
// ===================================
// author: M_sea
// website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=500000+10,L=1000001,M=L+10;
int n,Q,a[N];
#define ls (o<<1)
#define rs (o<<1|1)
int minv[M<<2],addv[M<<2],cntv[M<<2];
void pushup(int o) {
if (minv[ls]==minv[rs]) minv[o]=minv[ls],cntv[o]=cntv[ls]+cntv[rs];
else if (minv[ls]<minv[rs]) minv[o]=minv[ls],cntv[o]=cntv[ls];
else minv[o]=minv[rs],cntv[o]=cntv[rs];
}
void pushdown(int o) {
if (addv[o]) {
addv[ls]+=addv[o],minv[ls]+=addv[o];
addv[rs]+=addv[o],minv[rs]+=addv[o];
addv[o]=0;
}
}
void modify(int o,int l,int r,int p,int w) {
if (l==r) { cntv[o]+=w; return; }
int mid=(l+r)>>1; pushdown(o);
if (p<=mid) modify(ls,l,mid,p,w);
else modify(rs,mid+1,r,p,w);
pushup(o);
}
void modify(int o,int l,int r,int ql,int qr,int w) {
if (ql<=l&&r<=qr) { addv[o]+=w,minv[o]+=w; return; }
int mid=(l+r)>>1; pushdown(o);
if (ql<=mid) modify(ls,l,mid,ql,qr,w);
if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
pushup(o);
}
int query(int o,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return minv[o]==1?cntv[o]:0;
int mid=(l+r)>>1,res=0; pushdown(o);
if (ql<=mid) res+=query(ls,l,mid,ql,qr);
if (qr>mid) res+=query(rs,mid+1,r,ql,qr);
pushup(o); return res;
}
#undef ls
#undef rs
void update(int l,int r,int w) {
if (l==r) return;
if (l>r) swap(l,r);
modify(1,0,L,l,r-1,w);
}
int main() {
n=read(),Q=read();
for (int i=1;i<=n;++i) a[i]=read();
a[0]=L,a[n+1]=0;
for (int i=0;i<=n;++i) update(a[i],a[i+1],1),modify(1,0,L,a[i],1);
while (Q--) {
int p=read(),w=read();
update(a[p-1],a[p],-1),update(a[p],a[p+1],-1),modify(1,0,L,a[p],-1);
a[p]=w;
update(a[p-1],a[p],1),update(a[p],a[p+1],1),modify(1,0,L,a[p],1);
printf("%d\n",query(1,0,L,1,L-1));
}
return 0;
}