#include <bits/stdc++.h>
using namespace std;
struct SegTree{
	vector<int> val;
	void build(){
		val.resize((1<<18)*2);
		for(int i=0;i<(1<<18)*2;++i){
			val[i]=INT_MIN;
		}
	}
	void modify(int x,int v){
		x+=(1<<18)-1;
		val[x]=v;
		while(x>0){
			x=(x-1)/2;
			val[x]=max(val[x*2+1],val[x*2+2]);
		}
	}
	int query(int lc,int rc,int x=0,int l=0,int r=(1<<18)){
		if(rc<=l||r<=lc){
			return INT_MIN;
		}
		if(lc<=l&&r<=rc){
			return val[x];
		}
		int mid=(l+r)/2;
		return max(query(lc,rc,x*2+1,l,mid),query(lc,rc,x*2+2,mid,r));
	}
}seg,seg2;
int n;
int b[210000];
int sum[210000];
int ans;
int main(){
	seg.build(),seg2.build();
	cin>>n;
	for(int i=0;i<n;++i){
		cin>>b[i];
		sum[i+1]=sum[i]+!b[i];
	}
	int q;
	cin>>q;
	vector<pair<int,int> > qs(q);
	for(int i=0;i<q;++i){
		cin>>qs[i].first>>qs[i].second;
	}
	sort(qs.begin(),qs.end());
	for(auto op:qs){
		int l=op.first,r=op.second;
		int v=r-l+1-2*(sum[r]-sum[l-1]);
		int res=max(0,seg.query(0,l));
		res+=v;
		int res2=seg2.query(l,r+1);
		if(res2!=INT_MIN){
			res2+=r-2*sum[r];
		}
		int ret=max(res,res2);
		ans=max(ret,ans);
		seg.modify(r,ret);
		seg2.modify(r,ret-r+2*sum[r]);
	}
	cout<<n-sum[n]-ans<<'\n';
	return 0;
}
### Prompt

Create a solution in cpp for 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 <bits/stdc++.h>
using namespace std;
struct SegTree{
	vector<int> val;
	void build(){
		val.resize((1<<18)*2);
		for(int i=0;i<(1<<18)*2;++i){
			val[i]=INT_MIN;
		}
	}
	void modify(int x,int v){
		x+=(1<<18)-1;
		val[x]=v;
		while(x>0){
			x=(x-1)/2;
			val[x]=max(val[x*2+1],val[x*2+2]);
		}
	}
	int query(int lc,int rc,int x=0,int l=0,int r=(1<<18)){
		if(rc<=l||r<=lc){
			return INT_MIN;
		}
		if(lc<=l&&r<=rc){
			return val[x];
		}
		int mid=(l+r)/2;
		return max(query(lc,rc,x*2+1,l,mid),query(lc,rc,x*2+2,mid,r));
	}
}seg,seg2;
int n;
int b[210000];
int sum[210000];
int ans;
int main(){
	seg.build(),seg2.build();
	cin>>n;
	for(int i=0;i<n;++i){
		cin>>b[i];
		sum[i+1]=sum[i]+!b[i];
	}
	int q;
	cin>>q;
	vector<pair<int,int> > qs(q);
	for(int i=0;i<q;++i){
		cin>>qs[i].first>>qs[i].second;
	}
	sort(qs.begin(),qs.end());
	for(auto op:qs){
		int l=op.first,r=op.second;
		int v=r-l+1-2*(sum[r]-sum[l-1]);
		int res=max(0,seg.query(0,l));
		res+=v;
		int res2=seg2.query(l,r+1);
		if(res2!=INT_MIN){
			res2+=r-2*sum[r];
		}
		int ret=max(res,res2);
		ans=max(ret,ans);
		seg.modify(r,ret);
		seg2.modify(r,ret-r+2*sum[r]);
	}
	cout<<n-sum[n]-ans<<'\n';
	return 0;
}
```