一开始连题解都看不懂，对着题解敲了一遍算是会了（

题意：给定一个序列，对于每次询问，输出把这位数改成另一个数后的LIS长度。

下面的方法是通过 离线+树状数组 的解法做的。

核心的思想是在每修改一位时，这一位前面和后面的序列是不变的，并且LIS可以拆分为以该位开头的LIS与以该位结尾的LIS，所以这一位前面的LIS长度以及这一位后面的LIS长度都可以利用起来。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
int read()
{
	unsigned n=0; int f=1; char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
	for(;'0'<=ch&&ch<='9';ch=getchar()) n=(n<<3)+(n<<1)+(ch^48);
	return f*n;
}
//#define DEBUG 1
const int N=5E5+5;
int n,m;
int h[N],b[N<<1],cnt,now;
int f[N],g[N],len,lis[N];
//f[i]-以i为终点的LIS长度
//g[i]-以i为起点的LIS长度
struct ask
{
	int id,x,val;
	int f,g;
}qu[N];
bool cmp1(ask a,ask b){return a.x==b.x?a.id<b.id:a.x<b.x;}
int res[N];
#define x(i) qu[i].x
#define F(i) qu[i].f
#define G(i) qu[i].g
#define res(i) res[qu[i].id]

int tree[N<<1];//维护1~x的数中dp值的最大值 
inline int lowbit(int x){return x&-x;}
inline void update(int x,int k){for(;x<=cnt;x+=lowbit(x)) tree[x]=max(tree[x],k);} 
inline int query(int x){int ans=0; for(;x;x-=lowbit(x)) ans=max(ans,tree[x]); return ans;}

inline void Solve()
{
	#ifdef DEBUG
	printf("Debuging...\n");
	#endif

	n=read(),m=read();
	for(int i=1;i<=n;i++) b[i]=h[i]=read();
	cnt=n;
	for(int i=1;i<=m;i++)
		qu[i].id=i,qu[i].x=read(),b[++cnt]=qu[i].val=read();
	//离散化 
	sort(b+1,b+cnt+1);
	cnt=unique(b+1,b+cnt+1)-b-1;
	for(int i=1;i<=n;i++) h[i]=lower_bound(b+1,b+cnt+1,h[i])-b;
	for(int i=1;i<=m;i++) qu[i].val=lower_bound(b+1,b+cnt+1,qu[i].val)-b;
	//dp处理f,g
	//f-> 1->i的最长上升子序列 
	memset(tree,0,sizeof(tree));
	for(int i=1;i<=n;i++) f[i]=query(h[i]-1)+1,update(h[i],f[i]);
	//g-> n->i的最长下降子序列 
		//我们将求h[n->i]的最长下降子序列，转化为求cnt-h[n->i]+1的最长上升子序列 
	memset(tree,0,sizeof(tree));
	for(int i=n;i>=1;i--) g[i]=query(cnt-h[i])+1,update(cnt-h[i]+1,g[i]);
	//求LIS的长度len，并找出LIS某一位中的可能的数的数量
	//过i点的LIS长度为 f[i]+g[i]-1 
	for(int i=1;i<=n;i++) len=max(len,f[i]+g[i]-1); 
	for(int i=1;i<=n;i++) if(f[i]+g[i]-1==len) ++lis[f[i]];//这位数可以在LIS的f[i]位，记录
	//离线处理询问
	sort(qu+1,qu+m+1,cmp1);//按x排序 
	//处理出改变第i位时的f[i] 
		//now-当前处理到的位的前一位 
		//now每推进一位就把该位的f[i]加入树状数组 
		//这样查询出的F(i)就是以i-1位结尾的LIS长度 
	memset(tree,0,sizeof(tree)),now=1;
	for(int i=1;i<=m;i++)
	{
		for(; now < qu[i].x ; update(h[now],f[now]),++now);
		F(i)=query(qu[i].val-1);
	}
	//处理出改变第i位时的g[i]，与上面同理 
	memset(tree,0,sizeof(tree)),now=n;
	for(int i=m;i>=1;i--)
	{
		for(; now > qu[i].x ; update(cnt-h[now]+1,g[now]),--now);
		G(i)=query(cnt-qu[i].val);
		if(F(i)+G(i)+1>len) res(i)=F(i)+G(i)+1;
	}
	//根据F(i)和G(i)情况分类讨论
	//i点修改后过i点的为 F(i)+G(i)+1
		//如果修改后过i点的LIS长度短于len，并且这个点是LIS该位上的唯一点，那么LIS只能将该位剔除，答案为len-1
		//否则取修前与修后LIS长度的最大值（增长的才能让答案更新） 
	for(int i=1;i<=m;i++)
	if(!res(i))
	{
		if( F(i)+G(i)+1<len && f[x(i)]+g[x(i)]-1==len && lis[f[x(i)]]==1) res(i)=len-1;
		else res(i)=max(F(i)+G(i)+1,len);
	}
	//输出结果 
	for(int i=1;i<=m;i++) printf("%d\n",res[i]);
	
	return ;
}
//#define FILES_IO 2
int main()
{
	#ifdef FILES_IO
	string FileName="test",ReadFile=FileName+".in",WriteFile=FileName+".out";
	freopen(ReadFile.c_str(),"r", stdin);
	freopen(WriteFile.c_str(),"w", stdout);
	#endif
	//srand((unsigned)time(0));
	//ios::sync_with_stdio(false);
	//cin.tie(0);

	int T=1;
	//scanf("%d",&T);
	for(;T--;)
		Solve();

	#ifdef FILES_IO
	fclose(stdin);
	fclose(stdout);
	#endif
	return 0;
}