rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,T,q,a[N],c[N],d[N],sum[N],ans;
void cf(int l,int r){c[l]++,c[r+1]--;}
struct zz
{
	int maxx,id;
	zz(){maxx=id=0;}
}s[N<<2];
void pls(zz &a,zz b,zz c)
{
	if(b.maxx>c.maxx)a.maxx=b.maxx,a.id=b.id;
	else a.maxx=c.maxx,a.id=c.id;
}
void pushup(int k){pls(s[k],s[k*2],s[k*2+1]);}
void update(int k,int l,int r,int x,int v)
{
	if(l==r&&l==x)
	{
		s[k].maxx=v;
		s[k].id=l;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)update(k*2,l,mid,x,v);
	else update(k*2+1,mid+1,r,x,v);
	pushup(k);
}
main()
{
	cin>>n>>m>>T>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1,l,r;i<=q;i++)
	{
		cin>>l>>r;
		if(l<r)cf(l+1,r); 
	}
	for(int i=1;i<=n;i++)c[i]+=c[i-1];
	for(int i=2;i<=n;i++)ans+=c[i]*(a[i]!=a[i-1]);
	for(int i=2;i<=n;i++)if(a[i]==a[i-1])d[i]=c[i];
	for(int i=1;i<=n;i++)sum[i]=d[i]+d[i+1],update(1,1,n,i,sum[i]);
	cout<<ans+q<<endl;
	for(int i=1;i<=T;i++)
	{
		int mx=s[1].maxx,id=s[1].id;
		ans+=mx;
		cout<<ans+q<<endl;
		update(1,1,n,id,sum[id]=0);
		if(id!=n)update(1,1,n,id+1,sum[id+1]-=d[id+1]);
		if(id!=1)update(1,1,n,id-1,sum[id-1]-=d[id]);
		d[id]=0;
		if(id!=n)d[id+1]=0;
	}
}