#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define ref(i,x,y)for(int i=x;i<=y;++i)
const int N=200001;
const int inf=1e9;
int read(){
	char c=getchar();int d=0,f=1;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
	for(;c>='0'&&c<='9';d=d*10+c-48,c=getchar());
	return d*f;
}
int n,m,s[N];
struct xint{int L,R;}p[N];
struct node{int x,y,S1,S2;}a[N*5];
bool cmp(xint a,xint b){return a.L<b.L;}
void build(int x,int y,int t){
	a[t].x=x;a[t].y=y;
	a[t].S1=a[t].S2=inf;
	if(x==y)return;int mid=(x+y)>>1;
	build(x,mid,t<<1);
	build(mid+1,y,t<<1|1);
}
void update(int x,int t,int s1,int s2){
	a[t].S1=min(a[t].S1,s1);
	a[t].S2=min(a[t].S2,s2);
	if(a[t].x==a[t].y)return;
	int mid=(a[t].x+a[t].y)>>1;
	if(x<=mid)update(x,t<<1,s1,s2);
	else update(x,t<<1|1,s1,s2);
}
int query(int x,int y,int t,int tp){
	if(x<=a[t].x&&a[t].y<=y)
		return tp?a[t].S2:a[t].S1;
	int mid=(a[t].x+a[t].y)>>1;
	int res=inf;
	if(x<=mid)res=min(res,query(x,y,t<<1,tp));
	if(y>mid)res=min(res,query(x,y,t<<1|1,tp));
	return res;
}
int main(){
	n=read();
	ref(i,1,n)s[i]=s[i-1]+read();
	m=read();
	ref(i,1,m)p[i].L=read(),p[i].R=read();
	sort(p+1,p+m+1,cmp);
	build(0,n,1);
	update(0,1,0-s[0],0-(0-s[0]));
	int ans=s[n];
	ref(i,1,m){
		int L=p[i].L-1,R=p[i].R;
		int res=query(0,L,1,0)+s[L]+(R-L)-(s[R]-s[L]);
		res=min(res,query(L+1,R-1,1,1)+R-s[R]);
		ans=min(ans,res+s[n]-s[R]);
		update(R,1,res-s[R],res-(R-s[R]));
	}
	printf("%d\n",ans);
}
### Prompt

Your challenge is to write 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 <algorithm>
using namespace std;
#define ref(i,x,y)for(int i=x;i<=y;++i)
const int N=200001;
const int inf=1e9;
int read(){
	char c=getchar();int d=0,f=1;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
	for(;c>='0'&&c<='9';d=d*10+c-48,c=getchar());
	return d*f;
}
int n,m,s[N];
struct xint{int L,R;}p[N];
struct node{int x,y,S1,S2;}a[N*5];
bool cmp(xint a,xint b){return a.L<b.L;}
void build(int x,int y,int t){
	a[t].x=x;a[t].y=y;
	a[t].S1=a[t].S2=inf;
	if(x==y)return;int mid=(x+y)>>1;
	build(x,mid,t<<1);
	build(mid+1,y,t<<1|1);
}
void update(int x,int t,int s1,int s2){
	a[t].S1=min(a[t].S1,s1);
	a[t].S2=min(a[t].S2,s2);
	if(a[t].x==a[t].y)return;
	int mid=(a[t].x+a[t].y)>>1;
	if(x<=mid)update(x,t<<1,s1,s2);
	else update(x,t<<1|1,s1,s2);
}
int query(int x,int y,int t,int tp){
	if(x<=a[t].x&&a[t].y<=y)
		return tp?a[t].S2:a[t].S1;
	int mid=(a[t].x+a[t].y)>>1;
	int res=inf;
	if(x<=mid)res=min(res,query(x,y,t<<1,tp));
	if(y>mid)res=min(res,query(x,y,t<<1|1,tp));
	return res;
}
int main(){
	n=read();
	ref(i,1,n)s[i]=s[i-1]+read();
	m=read();
	ref(i,1,m)p[i].L=read(),p[i].R=read();
	sort(p+1,p+m+1,cmp);
	build(0,n,1);
	update(0,1,0-s[0],0-(0-s[0]));
	int ans=s[n];
	ref(i,1,m){
		int L=p[i].L-1,R=p[i].R;
		int res=query(0,L,1,0)+s[L]+(R-L)-(s[R]-s[L]);
		res=min(res,query(L+1,R-1,1,1)+R-s[R]);
		ans=min(ans,res+s[n]-s[R]);
		update(R,1,res-s[R],res-(R-s[R]));
	}
	printf("%d\n",ans);
}
```