记录编号	484160	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 序列	最终得分	100
用户昵称	泪寒之雪	是否通过	通过
代码语言	C++	运行时间	0.864 s
提交时间	2018-01-22 10:21:02	内存使用	3.15 MiB

#pragma GCC optimize("-O2")
#include<bits/stdc++.h>
#define getchar nc
#define sight(c) ('0'<=c&&c<='9')
#define swap(a,b) a^=b,b^=a,a^=b
#define LL long long
#define deg printf
#define dput put
#define dputc putchar
#define db double 
#define N 100007
#define eho(x) for(int i=head[x];i;i=net[i])
inline char nc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
    static char c;
    for (c=getchar();!sight(c);c=getchar());
    for (x=0;sight(c);c=getchar())x=x*10+c-48;
}
void write(int x){if (x<10) {putchar('0'+x); return;} write(x/10); putchar('0'+x%10);}
inline void writeln(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar('\n'); }
inline void writel(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); }
using namespace std;
#define Mid (l+r>>1)
struct Tre{
	#define L(x) x&-x
	#define max(a,b) (a>b?a:b)
	int s[N],n;
	void in(int x,int dla) {for (;x<n;x+=L(x)) s[x]=max(dla,s[x]);}
	int ask(int x) {static int L;for (L=0;x;x-=L(x)) L=max(s[x],L); return L;}
	void clear(int x) {for (;x<n;x+=L(x)) s[x]=0;}
	#undef max
	#undef L
}Tree;
struct No{
	int a,b,c;
	bool operator <(const No& A)const{
	   return A.b^b?(b<A.b):(a<A.a);
	}
}p[N];
int b[N],c[N],x,y,f[N],n,m;
void cqh(int l,int r){
	if (l==r) return;
	cqh(l,Mid);
	for (int i=l;i<=r;i++) p[i].a=i,p[i].b=b[i],p[i].c=c[i];
	sort(p+l,p+r+1);
	for (int i=l;i<=r;i++) 
	  if (p[i].a<=Mid) Tree.in(p[i].c,f[p[i].a]);
	  else f[p[i].a]=max(Tree.ask(p[i].c)+1,f[p[i].a]);
	for (int i=l;i<=Mid;i++) Tree.clear(c[i]);  
	cqh(Mid+1,r);
}
signed main() {
	freopen("heoi2016_seq.in","r",stdin);
	freopen("heoi2016_seq.out","w",stdout);
    read(n); read(m);
    Tree.n=n+3;
    for (int i=1;i<=n;i++) read(b[i]),c[i]=b[i],f[i]=1;
    while (m--) {
    	read(x); read(y);
    	if (y>b[x]) b[x]=y; if (y<c[x]) c[x]=y;
	}
	cqh(1,n);
	int ans=0;
	for (int i=1;i<=n;i++) ans=max(ans,f[i]);
	writeln(ans);
	return 0;
}