#include<bits/stdc++.h> #define ull unsigned long long #define PII pair<int,int> #define mk make_pair #define fi first #define se second using namespace std; const int N=1e6+10; const int INF=1e9+10; int c0=0,c1=0; bool g[N];int n,m,q; int a[N]; vector<PII> t[N]; vector<int> A[2],B[2]; PII operator+(PII a,PII b){ return mk(a.fi+b.fi,a.se+b.se); } struct segtree{ #define ls p*2 #define rs p*2+1 #define mid (l+r)/2 int T[N<<2],S[N<<2]; inline void pu(int p){ T[p]=T[ls]+T[rs]; S[p]=S[ls]+S[rs]; }inline void upd(int p,int l,int r,int x,int v){ if(l==r){ T[p]+=v;S[p]+=v*l;return ; }if(x<=mid) upd(ls,l,mid,x,v); else upd(rs,mid+1,r,x,v);pu(p); }inline PII qry(int p,int l,int r,int cnt){ if(l==r) return mk(min(cnt/l,T[p]),min(cnt/l,T[p])*l); if(S[ls]<=cnt) return mk(T[ls],S[ls])+qry(rs,mid+1,r,cnt-S[ls]); else return qry(ls,l,mid,cnt); } }SGT[2]; int sl,sr,cl,cr; set<int> s; int ans=0; inline void add(int p){ auto it=s.upper_bound(p); if(it!=s.end()){ if(a[*it]!=a[p]) ans++; else if(*it-p-1!=0) SGT[a[p]].upd(1,1,n,*it-p-1,1),ans+=2; } }inline void redo(int p){ auto it=s.upper_bound(p); if(it!=s.end()){ if(a[*it]!=a[p]) ans--; else if(*it-p-1!=0) SGT[a[p]].upd(1,1,n,*it-p-1,-1),ans-=2; } }inline void ins(int p){ auto it=s.lower_bound(p); if(it!=s.begin()){ --it; redo(*it); } s.insert(p); it=s.lower_bound(p); if(it!=s.begin()){ --it; add(*it); }add(p); }inline void del(int p){ auto it=s.lower_bound(p); if(it!=s.begin()){ --it; redo(*it); }redo(p); s.erase(p); it=s.lower_bound(p); if(it!=s.begin()){ --it; add(*it); } }int ct[2],t0=0,t1=0; int main(){ //double C=clock(); scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++){ int x;scanf("%d",&x); if(x%2==0) c0++;else c1++; } for(int i=1;i<=m;i++){ int p,b;scanf("%d%d",&p,&b); if(g[p]==1) del(p); if(g[p]==1) if(a[p]==0) t0--;else t1--; g[p]=1;a[p]=b%2; if(a[p]==0) t0++;else t1++; ins(p); if(s.size()!=0) sl=*s.begin()-1,sr=n-*(--s.end()),cl=a[*s.begin()],cr=a[*(--s.end())]; }while(q--){ int op,p,c;scanf("%d%d",&op,&p); if(op==2) scanf("%d",&c); if(op==1){ if(g[p]!=0) del(p); if(g[p]!=0) if(a[p]==0) t0--;else t1--; g[p]=0; if(s.size()!=0) sl=*s.begin()-1,sr=n-*(--s.end()),cl=a[*s.begin()],cr=a[*(--s.end())]; }else{ if(g[p]==1) del(p); if(g[p]==1) if(a[p]==0) t0--;else t1--; g[p]=1,a[p]=c%2; ins(p); if(a[p]==0) t0++;else t1++; if(s.size()!=0) sl=*s.begin()-1,sr=n-*(--s.end()),cl=a[*s.begin()],cr=a[*(--s.end())]; }//cout<<ans<<' '; if(s.size()==0){ if(max(c0,c1)==n) printf("%d\n",0); else printf("%d\n",1); }else{ ct[0]=c0-t0;ct[1]=c1-t1; PII R0=SGT[0].qry(1,1,n,ct[0]),R1=SGT[1].qry(1,1,n,ct[1]); int tmp=-2*(R0.fi+R1.fi); ct[0]-=R0.se,ct[1]-=R1.se; if(ct[cl]>=sl) ct[cl]-=sl; else tmp++; if(ct[cr]>=sr) ct[cr]-=sr; else tmp++; printf("%d\n",ans+tmp); } }//cerr<<(clock()-C)/CLOCKS_PER_SEC; return 0; }