Problem: You are given a sequence a = \\{a_1, ..., a_N\\} with all zeros, and a sequence b = \\{b_1, ..., b_N\\} consisting of 0 and 1. The length of both is N.

You can perform Q kinds of operations. The i-th operation is as follows:

* Replace each of a_{l_i}, a_{l_i + 1}, ..., a_{r_i} with 1.



Minimize the hamming distance between a and b, that is, the number of i such that a_i \neq b_i, by performing some of the Q operations.

Constraints

* 1 \leq N \leq 200,000
* b consists of 0 and 1.
* 1 \leq Q \leq 200,000
* 1 \leq l_i \leq r_i \leq N
* If i \neq j, either l_i \neq l_j or r_i \neq r_j.

Input

Input is given from Standard Input in the following format:


N
b_1 b_2 ... b_N
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q


Output

Print the minimum possible hamming distance.

Examples

Input

3
1 0 1
1
1 3


Output

1


Input

3
1 0 1
2
1 1
3 3


Output

0


Input

3
1 0 1
2
1 1
2 3


Output

1


Input

5
0 1 0 1 0
1
1 5


Output

2


Input

9
0 1 0 1 1 1 0 1 0
3
1 4
5 8
6 7


Output

3


Input

15
1 1 0 0 0 0 0 0 1 0 1 1 1 0 0
9
4 10
13 14
1 7
4 14
9 11
2 6
7 8
3 12
7 13


Output

5


Input

10
0 0 0 1 0 0 1 1 1 0
7
1 4
2 5
1 3
6 7
9 9
1 5
7 9


Output

1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 1000007
#define INF63 1061109567
#define INF127 9187201950435737471
#define UINF 18446744073709551615
#define F first
#define S second
#define ll long long
#define N 800010
using namespace std;
ll n,q,bin[N],sum[N],dp,val[N][2];
vector<pair<ll,ll> > vp;
void update(ll x,ll tl,ll tr,ll l,ll r,ll v,ll num)
{
	if(l<=tl&&r>=tr)
	{
		val[x][num]=max(val[x][num],v);
		return;
	}
	ll mid=(tl+tr)>>1;
	ll nl=x+((mid-tl+1)<<1);
	if(l<=mid)
	{
		update(x+1,tl,mid,l,r,v,num);
	}
	if(r>mid)
	{
		update(nl,mid+1,tr,l,r,v,num);
	}
	val[x][num]=max(val[x+1][num],val[nl][num]);
	return;
}
ll getans(ll x,ll tl,ll tr,ll l,ll r,ll num)
{
	if(l<=tl&&r>=tr)
	{
		return val[x][num];
	}
	ll mid=(tl+tr)>>1,ret;
	ll nl=x+((mid-tl+1)<<1);
	if(r<=mid)
	{
		ret=getans(x+1,tl,mid,l,r,num);
	}
	else if(l>mid)
	{
		ret=getans(nl,mid+1,tr,l,r,num);
	}
	else
	{
		ret=max(getans(x+1,tl,mid,l,r,num),getans(nl,mid+1,tr,l,r,num));
	}
	val[x][num]=max(val[x+1][num],val[nl][num]);
	return ret;
}
int main(){
	ll i,x,y,ans=0;
	cin>>n;
	memset(val,-127,sizeof(val));
	sum[0]=0;
	for(i=0;i<n;i++)
	{
		cin>>bin[i];
		if(bin[i]==1)
		{
			sum[i+1]=sum[i]+1;
		}
		else
		{
			sum[i+1]=sum[i]-1;
		}
	}
	cin>>q;
	while(q--)
	{
		cin>>x>>y;
		vp.push_back(make_pair(x,y));
	}
	sort(vp.begin(),vp.end());
	update(0,0,n-1,0,0,0,0);
	for(i=0;i<vp.size();i++)
	{
		x=vp[i].F;
		y=vp[i].S;
		dp=max(sum[y]-sum[x-1]+getans(0,0,n-1,0,x-1,0),sum[y]+getans(0,0,n-1,x,y,1));
		update(0,0,n-1,y,y,dp,0);
		update(0,0,n-1,y,y,dp-sum[y],1);
		ans=max(ans,dp);
	}
	for(i=0;i<n;i++)
	{
		if(bin[i]==0)
		{
			ans++;
		}
	}
	cout<<n-ans<<endl;
	return 0;
}