#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<set>
#include<vector>
#include<map>
#include<queue>
 
#define N 200005
#define M 8000005
 
#define ls (t<<1)
#define rs ((t<<1)|1)
#define mid ((l+r)>>1)
 
#define mk make_pair
#define pb push_back
#define fi first
#define se second
 
#define Mo 1000000007
 
using namespace std;
 
int i,j,m,n,p,k,s[N],q,l,r,g[N];
 
vector<int>v[N];
 
int f[N],tree[N*4];
 
int ask(int ll,int l,int r,int t)
{
		if (l==r) return tree[t];
		else 
		{
				if (ll<=mid) return min(tree[t],ask(ll,l,mid,ls));
				else return min(tree[t],ask(ll,mid+1,r,rs));
		}
}
 
void insert(int ll,int rr,int c,int l,int r,int t)
{
		if (ll<=l&&r<=rr) tree[t]=min(tree[t],c);
		else 
		{
				if (ll<=mid) insert(ll,rr,c,l,mid,ls);
				if (rr>mid)  insert(ll,rr,c,mid+1,r,rs);
		}
}
 
 
void build_tree(int l,int r,int t)
{
		tree[t]=(int)1e9;
		if  (l==r) return;
		build_tree(l,mid,ls);
		build_tree(mid+1,r,rs);
}
 
int main()
{
		scanf("%d",&n);
		for (i=1;i<=n;++i) scanf("%d",&s[i]),s[i]+=s[i-1];
		scanf("%d",&q);
		for (i=1;i<=q;++i) 
			scanf("%d%d",&l,&r),v[r].pb(l);
		memset(f,60,sizeof(f));
		memset(g,60,sizeof(g));
		f[0]=0; g[0]=0;
		build_tree(0,n,1);
		for (i=1;i<=n;++i)
		{
				g[i]=min(g[i-1],f[i-1])+(s[i]-s[i-1]==1);
				int G;
				for (int j: v[i])
					G=min(g[j-1]+(i-s[i])-(j-1-s[j-1]),(i-s[i])+ask(j-1,0,n,1)),
					insert(j,i,-(i-s[i])+G,0,n,1),
					f[i]=min(f[i],G);
		}
		printf("%d\n",min(f[n],g[n]));
}
### Prompt

Please create a solution in CPP 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<algorithm>
#include<cstring>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<set>
#include<vector>
#include<map>
#include<queue>
 
#define N 200005
#define M 8000005
 
#define ls (t<<1)
#define rs ((t<<1)|1)
#define mid ((l+r)>>1)
 
#define mk make_pair
#define pb push_back
#define fi first
#define se second
 
#define Mo 1000000007
 
using namespace std;
 
int i,j,m,n,p,k,s[N],q,l,r,g[N];
 
vector<int>v[N];
 
int f[N],tree[N*4];
 
int ask(int ll,int l,int r,int t)
{
		if (l==r) return tree[t];
		else 
		{
				if (ll<=mid) return min(tree[t],ask(ll,l,mid,ls));
				else return min(tree[t],ask(ll,mid+1,r,rs));
		}
}
 
void insert(int ll,int rr,int c,int l,int r,int t)
{
		if (ll<=l&&r<=rr) tree[t]=min(tree[t],c);
		else 
		{
				if (ll<=mid) insert(ll,rr,c,l,mid,ls);
				if (rr>mid)  insert(ll,rr,c,mid+1,r,rs);
		}
}
 
 
void build_tree(int l,int r,int t)
{
		tree[t]=(int)1e9;
		if  (l==r) return;
		build_tree(l,mid,ls);
		build_tree(mid+1,r,rs);
}
 
int main()
{
		scanf("%d",&n);
		for (i=1;i<=n;++i) scanf("%d",&s[i]),s[i]+=s[i-1];
		scanf("%d",&q);
		for (i=1;i<=q;++i) 
			scanf("%d%d",&l,&r),v[r].pb(l);
		memset(f,60,sizeof(f));
		memset(g,60,sizeof(g));
		f[0]=0; g[0]=0;
		build_tree(0,n,1);
		for (i=1;i<=n;++i)
		{
				g[i]=min(g[i-1],f[i-1])+(s[i]-s[i-1]==1);
				int G;
				for (int j: v[i])
					G=min(g[j-1]+(i-s[i])-(j-1-s[j-1]),(i-s[i])+ask(j-1,0,n,1)),
					insert(j,i,-(i-s[i])+G,0,n,1),
					f[i]=min(f[i],G);
		}
		printf("%d\n",min(f[n],g[n]));
}
```