#include<bits/stdc++.h> using namespace std; // #define int long long int c[2]; set<int>S; map<int,int>mp; int n,m,q; int df=0; int w[1<<21][2],s[1<<21][2]; int C=(1<<20)-1; int aw=0; inline void mod(int c,int k,bool tp){ if(c==0){aw+=k;return ;} int x=C+c; while(x){ w[x][tp]+=k; s[x][tp]+=c*k; x>>=1; } } inline void add(bool p,bool q,int l,int k){ if(p!=q)df+=k; else mod(l,k,p); } inline void del(int p){ auto it=S.lower_bound(p); int a=-1,b=-1; c[mp[p]]++; if(it!=S.begin()){ it--; a=*it; add(mp[a],mp[p],p-a-1,-1); it++; } it++; if(it!=S.end()){ b=*it; add(mp[p],mp[b],b-p-1,-1); } it--; if(a!=-1&&b!=-1) add(mp[a],mp[b],b-a-1,1); S.erase(p); mp.erase(p); } inline void ins(int p,int x){ c[x]--; S.insert(p); mp[p]=x; auto it=S.lower_bound(p); int a=-1,b=-1; if(it!=S.begin()){ it--; a=*it; add(mp[a],mp[p],p-a-1,1); it++; } it++; if(it!=S.end()){ b=*it; add(mp[p],mp[b],b-p-1,1); } it--; if(a!=-1&&b!=-1) add(mp[a],mp[b],b-a-1,-1); } inline void mod(int p,int x){ if(S.count(p)) del(p); if(x==-1)return ; ins(p,x); } #define lc(x) (x<<1) #define rc(x) (x<<1|1) inline int g(int x,int l,int r,int tp,int rem){ if(s[x][tp]<=rem)return w[x][tp]; if(l==r)return min(rem/l,w[x][tp]); int mid=l+r>>1; if(s[lc(x)][tp]<=rem)return w[lc(x)][tp]+g(rc(x),mid+1,r,tp,rem-s[lc(x)][tp]); else return g(lc(x),l,mid,tp,rem); } inline int rcalc(){ return 2*(S.size()+1)-df-2*(g(1,1,1<<20,0,c[0])+g(1,1,1<<20,1,c[1])+aw); } inline int calc(){ if(S.empty()){ if(c[0]==n||c[1]==n)return 0; return 1; } int x=*S.begin(),y=*S.rbegin(); int res=1e9; add(0,mp[x],x-1,1); add(0,mp[y],n-y,1); res=min(res,rcalc()); add(0,mp[y],n-y,-1); add(1,mp[y],n-y,1); res=min(res,rcalc()); add(0,mp[x],x-1,-1); add(1,mp[x],x-1,1); res=min(res,rcalc()); add(1,mp[y],n-y,-1); add(0,mp[y],n-y,1); res=min(res,rcalc()); add(0,mp[y],n-y,-1); add(1,mp[x],x-1,-1); return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("b.in","r",stdin); // freopen("b.out","w",stdout); // int CC=clock(); cin>>n>>m>>q; for(int i=1;i<=n;i++){ int x; cin>>x; c[x&1]++; } while(m--){ int p,x; cin>>p>>x; x%=2; // cerr<<p<<" "<<x<<endl; mod(p,x); } // return 0; while(q--){ int op,p; cin>>op>>p; if(op==1) mod(p,-1); else { int x; cin>>x; mod(p,x&1); } // cout<<2*(S.size()+1)<<" "; cout<<calc()<<"\n"; } // cerr<<(clock()-CC)*1000/CLOCKS_PER_SEC<<endl; cout.flush(); return 0; } /* ulimit -v 512000 -s -v */