把pos[i]上出现的平常值定义为nor[i]最大值定义为max[i]最小值定义为min[i]，那么我们发现在两个值,i（前）,j（后）,当且仅当max[i]<=nor[j],nor[i]<=min[j]时才会组成序列的前后两个值，并且当序列里所有连续的两个值都满足这个条件是时就可以，因此我们以f[i]表示以i为起点的序列最长值，那么我们就可以转移了f[i]=maxf[j](max[i]<=nor[j],nor[i]<=min[j],pos[i]<pos[j])+1,这就是一个三维逆序对，至于pos[i]我们用默认时间来维护（按倒序插入），用一颗值域线段树来维护nor[i]值域并在每个节点中建一颗替罪羊树表示在nor在此值域里的数，并用min值排序，并且在每个替罪羊节点上维护最大值标记（表示是子树里表示的点里f最大值）
用树套树解决三维偏序的一般思路：一维用时间维护，一维用线段树来维护，另一位用线段树里的平衡排序维护
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstring>
#define MAXN 100000
using namespace std;
inline int read()
{
int sum=;
char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<='')
{
sum=(sum<<)+(sum<<)+ch-'';
ch=getchar();
}
return sum;
}
inline int MAX(int x,int y)
{
return x>y?x:y;
}
inline int MIN(int x,int y)
{
return x<y?x:y;
}
const double alpha=0.75;
struct ScapeGoat_Tree
{
ScapeGoat_Tree *ch[];
int key,size,f,Max;
void pushup()
{
size=ch[]->size++ch[]->size;
Max=ch[]->Max>ch[]->Max?ch[]->Max:ch[]->Max;
Max=Max>f?Max:f;
}
bool isbad()
{
return alpha*size+<ch[]->size||alpha*size+<ch[]->size;
}
}*null,Node[MAXN<<],*list[MAXN<<];
int top,len;
inline void ScapeGoat_Tree_Init()
{
null=Node;
null->ch[]=null->ch[]=null;
}
inline ScapeGoat_Tree *NEW(int key,int F)
{
ScapeGoat_Tree *p=&Node[++top];
p->ch[]=p->ch[]=null;
p->size=;
p->key=key;
p->f=p->Max=F;
return p;
}
void travel(ScapeGoat_Tree *p)
{
if(p==null)return;
travel(p->ch[]);
list[++len]=p;
travel(p->ch[]);
}
ScapeGoat_Tree *divide(int l,int r)
{
if(l>r)return null;
int mid=(l+r)>>;
list[mid]->ch[]=divide(l,mid-);
list[mid]->ch[]=divide(mid+,r);
list[mid]->pushup();
return list[mid];
}
inline void rebuild(ScapeGoat_Tree *&p)
{
len=;
travel(p);
p=divide(,len);
}
ScapeGoat_Tree **insert(ScapeGoat_Tree *&p,int key,int F)
{
if(p==null)
{
p=NEW(key,F);
return &null;
}
ScapeGoat_Tree **ret=insert(p->ch[p->key<key],key,F);
p->pushup();
if(p->isbad())ret=&p;
return ret;
}
inline void Insert(ScapeGoat_Tree *&Root,int key,int F)
{
ScapeGoat_Tree **p=insert(Root,key,F);
if(*p!=null)rebuild(*p);
}
inline int get_Rank(ScapeGoat_Tree *Root,int key)
{
ScapeGoat_Tree *p=Root;
int ret=;
while(p!=null)
if(p->key>=key)
p=p->ch[];
else
ret+=p->ch[]->size+,p=p->ch[];
return ret;
}
int get_Max(ScapeGoat_Tree *p,int l)
{
if(l>p->size)return ;
if(l<=) return p->Max;
int ans=;
if(l<=p->ch[]->size)ans=get_Max(p->ch[],l);
if(l<=p->ch[]->size+)ans=MAX(ans,p->f);
ans=MAX(ans,get_Max(p->ch[],l-p->ch[]->size-));
return ans;
}
inline int query(ScapeGoat_Tree *Root,int key)
{
return get_Max(Root,get_Rank(Root,key)+);
}
struct Seg_Tree
{
ScapeGoat_Tree *root;
int l,r,mid;
Seg_Tree *ch[];
}node[MAXN<<],*root;
int sz;
inline Seg_Tree *New(int l,int r)
{
Seg_Tree *p=&node[sz++];
p->l=l;
p->r=r;
p->mid=(l+r)>>;
p->root=null;
return p;
}
void build(Seg_Tree *p)
{
if(p->l==p->r)return;
p->ch[]=New(p->l,p->mid);
p->ch[]=New(p->mid+,p->r);
build(p->ch[]);
build(p->ch[]);
}
inline void Seg_Tree_Init()
{
root=New(,MAXN);
build(root);
}
void Ins(Seg_Tree *p,int pos,int key,int F)
{
Insert(p->root,key,F);
if(p->l==p->r)return;
Ins(p->ch[p->mid<pos],pos,key,F);
}
int Query(Seg_Tree *p,int l,int key)
{
if(l<=p->l)
return query(p->root,key);
int ans=;
if(l<=p->mid) ans=Query(p->ch[],l,key);
ans=MAX(ans,Query(p->ch[],l,key));
return ans;
}
int n,m;
int Max[MAXN+],Min[MAXN+],nor[MAXN+],f[MAXN+];
inline void Init()
{
ScapeGoat_Tree_Init();
Seg_Tree_Init();
n=read(),m=read();
for(int i=;i<=n;i++)Max[i]=Min[i]=nor[i]=read();
for(int i=;i<=m;i++)
{
int x=read(),y=read();
Max[x]=MAX(y,Max[x]);
Min[x]=MIN(y,Min[x]);
}
}
inline void WORK()
{
f[n]=;
Ins(root,nor[n],Min[n],);
int ans=;
for(int i=n-;i>;i--)
{
f[i]=Query(root,Max[i],nor[i])+;
Ins(root,nor[i],Min[i],f[i]);
ans=MAX(f[i],ans);
}
printf("%d",ans);
}
int main()
{
Init();
WORK();
}