WA0pts 求调

#include<bits/stdc++.h>

using namespace std;

const int N=100005;

int n,m;

struct Tre {
	int l,r;
	int max=0;
}tre[4*N];

#define mid ((tre[now].l+tre[now].r)/2)
#define lson (now*2)
#define rson (now*2+1)

void pushup(int now) {tre[now].max=max(tre[lson].max,tre[rson].max);}

void build(int now,int l,int r) {
	tre[now].l=l,tre[now].r=r;
	if(l==r) return;
	build(lson,l,mid);
	build(rson,mid+1,r);
}

void change(int now,int p,int val) {
	if(tre[now].l==p && tre[now].r==p) {
		tre[now].max=max(tre[now].max,val);
//		cout << tre[now].l << ' ' << tre[now].max << endl;
		return;
	}
	if(tre[lson].r>=p) change(lson,p,val);
	else change(rson,p,val);
	pushup(now);
}

void clear(int now,int p) {
	if(tre[now].l==p && tre[now].r==p) {tre[now].max=0;return;}
	if(tre[lson].r>=p) clear(lson,p);
	else clear(rson,p);
	pushup(now);
}

int query(int now,int l,int r) {
	if(tre[now].l>r || tre[now].r<l) return 0;
	if(tre[now].l>=l && tre[now].r<=r) return tre[now].max;
	return max(query(lson,l,r),query(rson,l,r));
}

struct Node {
	int val,max,min,id,dp=0;
}arr[N];

bool cmp_max(Node a,Node b) {return a.max<b.max;}
bool cmp_val(Node a,Node b) {return a.val<b.val;}
bool cmp_id(Node a,Node b) {return a.id<b.id;}

void CDQ(int l,int r) {
	if(l==r) {arr[l].dp=max(arr[l].dp,1);return;}
//	cout << l << ' ' << r << endl;
	int Mid=l+r>>1;
	CDQ(l,Mid);
	sort(arr+l+1,arr+Mid+1,cmp_max);
	sort(arr+Mid+1,arr+r+1,cmp_val);
	int p=l;
	for(int i=Mid+1;i<=r;++i) {
		while(p<=Mid && arr[p].max<=arr[i].val) {
			change(1,arr[p].val,arr[p].dp);
			p++;
		}
		arr[i].dp=max(arr[i].dp,query(1,1,arr[i].min)+1);
//		cout << l << ' ' << r << ' ' << arr[i].id << ' ' << arr[i].dp << endl;
	}
	for(int i=l;i<=Mid;++i) clear(1,arr[p].val); 
	sort(arr+Mid+1,arr+r+1,cmp_id);
	CDQ(Mid+1,r);
}

int main() {
	cin >> n >> m;
	for(int i=1;i<=n;i++) {cin >> arr[i].val;arr[i].min=arr[i].max=arr[i].val;}
	
	int x,y;
	for(int i=1;i<=m;++i,arr[x].max=max(arr[x].max,y),arr[x].min=min(arr[x].min,y)) cin >> x >> y;
	for(int i=1;i<=n;++i) arr[i].id=i;
	
	build(1,1,n);
	CDQ(1,n);
	
	int ans=0;
	for(int i=1;i<=n;++i) ans=max(ans,arr[i].dp);
	cout << ans;
	
	return 0;
}