#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cctype>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iomanip>
#include<sstream>
#include<cstdlib>
#include<ctime>
#include<list>
#include<deque>
#include<bitset>
#include<fstream>
#define ld double
#define ull unsigned long long 
#define ll long long 
#define pii pair<int,int >
#define iiii pair<int,pii >
#define mp make_pair 
#define INF 1000000000
#define MOD 1000000007 
#define rep(i,x) for(int (i)=0;(i)<(x);(i)++)

using namespace std;

inline int getint()
{
	int x=0,p=1;char c;
	c=getchar();
	while (c<=32)c=getchar();
	if(c==45)p=-p,c=getchar();
	while (c>32)x=x*10+c-48,c=getchar();
	return x*p;
}

const int maxn=2e5+5;
int n,m=1,dat[4*maxn],a[maxn],cnt,dp[maxn],t;
vector<pii >v;


void fM(int k,int x)
{
	k+=m-1;
	dat[k]=x;
	while (k>0)
	{
		k=(k-1)/2;
		dat[k]=min(dat[2*k+1],dat[2*k+2]);
	}
}
int fQ(int x,int y,int l,int r,int k)
{
	if(y<=l||x>=r)return INF;
	else if(x<=l&&r<=y)return dat[k];
	else
	{
		int lx=fQ(x,y,l,(l+r)>>1,2*k+1);
		int ly=fQ(x,y,(l+r)>>1,r,2*k+2);
		return min(lx,ly);
	}
}


int main()
{
	n=getint();
	while (m<n+1)m<<=1;
	for(int i=0;i<2*m-1;i++)dat[i]=INF;
	for(int i=1;i<=n;i++)dp[i]=INF;
	 
	for(int i=1;i<=n;i++)
	{
	 	a[i]=getint();
	 	if(!a[i])a[i]--,dp[0]++;
	}
	 
	t=getint();
	rep(i,t)
	{
	 	int x=getint(),y=getint();
	 	v.push_back(mp(x,-y));
	}
	 
	sort(v.begin(),v.end());
	fM(0,dp[0]);

	 
	int p=0;
	for(int i=1;i<=n;i++)
	{
	 	while(p<t&&v[p].first==i)
		{
			int y=-v[p++].second;
			dp[y]=fQ(i-1,y+1,0,m,0);
			fM(y,dp[y]);
		}
		dp[i]=min(dp[i-1]+a[i],dp[i]);
		fM(i,dp[i]);
	}
	 
	printf("%d\n",dp[n]);

	return 0;	
} 
### Prompt

Please formulate a CPP solution to the following 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

### Response

```cpp
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cctype>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iomanip>
#include<sstream>
#include<cstdlib>
#include<ctime>
#include<list>
#include<deque>
#include<bitset>
#include<fstream>
#define ld double
#define ull unsigned long long 
#define ll long long 
#define pii pair<int,int >
#define iiii pair<int,pii >
#define mp make_pair 
#define INF 1000000000
#define MOD 1000000007 
#define rep(i,x) for(int (i)=0;(i)<(x);(i)++)

using namespace std;

inline int getint()
{
	int x=0,p=1;char c;
	c=getchar();
	while (c<=32)c=getchar();
	if(c==45)p=-p,c=getchar();
	while (c>32)x=x*10+c-48,c=getchar();
	return x*p;
}

const int maxn=2e5+5;
int n,m=1,dat[4*maxn],a[maxn],cnt,dp[maxn],t;
vector<pii >v;


void fM(int k,int x)
{
	k+=m-1;
	dat[k]=x;
	while (k>0)
	{
		k=(k-1)/2;
		dat[k]=min(dat[2*k+1],dat[2*k+2]);
	}
}
int fQ(int x,int y,int l,int r,int k)
{
	if(y<=l||x>=r)return INF;
	else if(x<=l&&r<=y)return dat[k];
	else
	{
		int lx=fQ(x,y,l,(l+r)>>1,2*k+1);
		int ly=fQ(x,y,(l+r)>>1,r,2*k+2);
		return min(lx,ly);
	}
}


int main()
{
	n=getint();
	while (m<n+1)m<<=1;
	for(int i=0;i<2*m-1;i++)dat[i]=INF;
	for(int i=1;i<=n;i++)dp[i]=INF;
	 
	for(int i=1;i<=n;i++)
	{
	 	a[i]=getint();
	 	if(!a[i])a[i]--,dp[0]++;
	}
	 
	t=getint();
	rep(i,t)
	{
	 	int x=getint(),y=getint();
	 	v.push_back(mp(x,-y));
	}
	 
	sort(v.begin(),v.end());
	fM(0,dp[0]);

	 
	int p=0;
	for(int i=1;i<=n;i++)
	{
	 	while(p<t&&v[p].first==i)
		{
			int y=-v[p++].second;
			dp[y]=fQ(i-1,y+1,0,m,0);
			fM(y,dp[y]);
		}
		dp[i]=min(dp[i-1]+a[i],dp[i]);
		fM(i,dp[i]);
	}
	 
	printf("%d\n",dp[n]);

	return 0;	
} 
```