1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

inline int getint() {
	int ret=0;bool ok=0;
	for(;;) {
		int c=getchar();
		if(c>='0'&&c<='9')ret=(ret<<3)+ret+ret+c-'0',ok=1;
		else if(ok)return ret;
	}
}

const int N=12000000,M=501000;
int rk[N],pl[N],pr[N],pre[N],cur;
int rt[M],nd[M],a[M],p1[M],p2[M],buf[M],ret[M],vl[M],vr[M];
int n,m;
int build(int l,int r) {
	int c=++cur;
	if (l==r) {
		rk[c]=a[l];
	} else {
		int md=(l+r)>>1;
		pl[c]=build(l,md);
		pr[c]=build(md+1,r);
	}
	return c;
}
int modify(int p,int l,int r,int x,int v) {
	int c=++cur; pre[c]=p;
	pl[c]=pl[p]; pr[c]=pr[p];
	if (l==r) rk[c]=v;
	else {
		int md=(l+r)>>1;
		if (x<=md) pl[c]=modify(pl[p],l,md,x,v);
		else pr[c]=modify(pr[p],md+1,r,x,v);
	}
	return c;
}
int solve(int p,int l,int r) {
	if (l==r) {
		int u=p,cnt=0;
		while (u) {
			nd[cnt++]=u;
			u=pre[u];
		}
		sort(nd,nd+cnt,[&](int a,int b) { return rk[a]<rk[b]; });
		int tot=0;
		rep(i,0,cnt) {
			int v=rk[nd[i]];
			rk[nd[i]]=tot;
			if (i!=cnt-1&&v!=rk[nd[i+1]]) tot++;
		}
		return tot+1;
	} else {
		int md=(l+r)>>1;
		int ls=solve(pl[p],l,md);
		int rs=solve(pr[p],md+1,r);
		int u=p,cnt=0;
		while (u) {
			nd[cnt]=u;
			vl[cnt]=rk[pl[u]];
			vr[cnt]=rk[pr[u]];
			++cnt;
			u=pre[u];
		}
		rep(i,0,rs) buf[i]=0;
		rep(i,0,cnt) buf[vr[i]]++;
		rep(i,1,rs) buf[i]+=buf[i-1];
		per(i,0,cnt) p1[--buf[vr[i]]]=i;
		rep(i,0,ls) buf[i]=0;
		rep(i,0,cnt) buf[vl[p1[i]]]++;
		rep(i,1,ls) buf[i]+=buf[i-1];
		per(i,0,cnt) p2[--buf[vl[p1[i]]]]=p1[i];
		int tot=0;
		rep(i,0,cnt) {
			if (i!=0&&(vl[p2[i]]!=vl[p2[i-1]]||vr[p2[i]]!=vr[p2[i-1]])) tot++;
			rk[nd[p2[i]]]=tot;
		}
		return tot+1;
	}
}
int main() {
	n=getint(); m=getint();
	rep(i,1,n+1) a[i]=getint();
	rt[1]=build(1,n);
	rep(i,2,m+1) {
		int t=getint(),v=getint();
		rt[i]=modify(rt[i-1],1,n,t,v);
	}
	solve(rt[m],1,n);
	rep(i,1,m+1) ret[i]=i;
	sort(ret+1,ret+m+1,[&](int a,int b) { return rk[rt[a]]==rk[rt[b]]?a<b:rk[rt[a]]<rk[rt[b]]; });
	rep(i,1,m+1) printf("%d%c",ret[i]," \n"[i==m]);
}