#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
 
struct segtree{
	using D = int;
	D inf = 1e9;
 
	int N;
	vector<D> val;
 
	segtree(){}
	segtree(int n){
		N=1;
		while(N<n) N*=2;
		val.assign(N*2,inf);
	}
	segtree(const vector<D>& ds){
		int n = ds.size();
		N=1;
		while(N<n) N*=2;
		val.assign(N*2,inf);
		rep(i,n) val[i+N] = ds[i];
		for(int i=N-1;i>0;i--) val[i] = min(val[i*2],val[i*2+1]);
	}
	void assign(int k,D d){
		k+=N;
		chmin(val[k],d);
		k/=2;
		while(k){
			val[k] = min(val[k*2],val[k*2+1]);
			k/=2;
		}
	}
	D getmin(int a,int b){
		D res = inf;
		a+=N,b+=N;
		while(a<b){
			if(a&1) chmin(res,val[a++]);
			if(b&1) chmin(res,val[--b]);
			a/=2,b/=2;
		}
		return res;
	}
};
 
int N;
int Q;
const int MN = 200010;
int b[MN];
int num0[MN],num1[MN];
int main(){
	cin>>N;
	rep(i,N) cin>>b[i];
	b[N] = 1;
	N++;
	rep(i,N){
		if(b[i]==0) num0[i+1]=1;
		else num1[i+1]=1;
	}
	rep(i,N){
		num0[i+1] += num0[i];
		num1[i+1] += num1[i];
	}
	cin>>Q;
	using P = pair<int,int>;
	vector<P> ps;
	rep(i,Q){
		int l,r;
		cin>>l>>r;
		l--;
		ps.pb(P(l,r));
	}
	ps.pb(P(N-1,N));
	sort(all(ps));
 
	segtree seg0(N),seg1(N);
 
	seg0.assign(0,0);
	seg1.assign(0,0);
 
	int ans = 0;
 
	for(P p:ps){
		int l = p.fs, r = p.sc;
		int val = 1e9;
		chmin(val,seg0.getmin(l,r)+num0[r]);
		chmin(val,seg1.getmin(0,l)+num1[l]+num0[r]-num0[l]);
		seg0.assign(r,val-num0[r]);
		seg1.assign(r,val-num1[r]);
		ans = val;
	}
	cout << ans << endl;
}
### 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 <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
 
struct segtree{
	using D = int;
	D inf = 1e9;
 
	int N;
	vector<D> val;
 
	segtree(){}
	segtree(int n){
		N=1;
		while(N<n) N*=2;
		val.assign(N*2,inf);
	}
	segtree(const vector<D>& ds){
		int n = ds.size();
		N=1;
		while(N<n) N*=2;
		val.assign(N*2,inf);
		rep(i,n) val[i+N] = ds[i];
		for(int i=N-1;i>0;i--) val[i] = min(val[i*2],val[i*2+1]);
	}
	void assign(int k,D d){
		k+=N;
		chmin(val[k],d);
		k/=2;
		while(k){
			val[k] = min(val[k*2],val[k*2+1]);
			k/=2;
		}
	}
	D getmin(int a,int b){
		D res = inf;
		a+=N,b+=N;
		while(a<b){
			if(a&1) chmin(res,val[a++]);
			if(b&1) chmin(res,val[--b]);
			a/=2,b/=2;
		}
		return res;
	}
};
 
int N;
int Q;
const int MN = 200010;
int b[MN];
int num0[MN],num1[MN];
int main(){
	cin>>N;
	rep(i,N) cin>>b[i];
	b[N] = 1;
	N++;
	rep(i,N){
		if(b[i]==0) num0[i+1]=1;
		else num1[i+1]=1;
	}
	rep(i,N){
		num0[i+1] += num0[i];
		num1[i+1] += num1[i];
	}
	cin>>Q;
	using P = pair<int,int>;
	vector<P> ps;
	rep(i,Q){
		int l,r;
		cin>>l>>r;
		l--;
		ps.pb(P(l,r));
	}
	ps.pb(P(N-1,N));
	sort(all(ps));
 
	segtree seg0(N),seg1(N);
 
	seg0.assign(0,0);
	seg1.assign(0,0);
 
	int ans = 0;
 
	for(P p:ps){
		int l = p.fs, r = p.sc;
		int val = 1e9;
		chmin(val,seg0.getmin(l,r)+num0[r]);
		chmin(val,seg1.getmin(0,l)+num1[l]+num0[r]-num0[l]);
		seg0.assign(r,val-num0[r]);
		seg1.assign(r,val-num1[r]);
		ans = val;
	}
	cout << ans << endl;
}
```