#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define N 262144
int dat[N*2+10],ad[N*2+10];
int inf=1000000000;
//[a,b)の最小値
//外からは(a,b,0,0,N)として呼ぶ
int query(int a,int b,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return inf;
	if(a<=l && r<=b) return dat[k]+ad[k];
	int vl=query(a,b,k*2+1,l,(l+r)/2);
	int vr=query(a,b,k*2+2,(l+r)/2,r);
	return ad[k]+min(vl,vr);
}
//[a,b)に加算する
void add(int a,int b,int x,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return;
	if(a<=l && r<=b) ad[k]+=x;
	else{
		add(a,b,x,k*2+1,l,(l+r)/2);
		add(a,b,x,k*2+2,(l+r)/2,r);
		dat[k]=min(dat[k*2+1]+ad[k*2+1],dat[k*2+2]+ad[k*2+2]);
	}
}
void update(int k,int a){
	k+=N-1;
	dat[k]=a;
	while(k>0){
		k=(k-1)/2;
		dat[k]=min(dat[k*2+1]+ad[k*2+1],dat[k*2+2]+ad[k*2+2]);
	}
	return;
}
//今kにどれくらいの数が加算されているのか
int cal(int k){
	k+=N-1;
	int ret=ad[k];
	while(k>0){
		k=(k-1)/2;ret+=ad[k];
	}
	return ret;
}
int b[200100];
vector<pint> v;
int main()
{
	int n,q,l,r;
	cin>>n;
	rep(i,n) cin>>b[i];
	cin>>q;
	rep(i,q){
		cin>>l>>r;l--;
		v.pb(mp(l,r));
	}
	v.pb(mp(0,0));v.pb(mp(n,n));sort(All(v));
	memset(ad,0,sizeof(ad));
	rep(i,N*2+10) dat[i]=inf;
	update(0,0);
	rep(i,q+1){
		REP(j,v[i].fi,v[i+1].fi){
			if(b[j]==0) add(j+1,n+10,1);
			else add(0,j+1,1);
		}
		if(i>=q) break;
		l=v[i+1].fi;r=v[i+1].se;
		int now=query(0,r+1),su=cal(r);
		update(r,now-su);
	}
	cout<<query(0,n+10)<<endl;
}

### 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<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define N 262144
int dat[N*2+10],ad[N*2+10];
int inf=1000000000;
//[a,b)の最小値
//外からは(a,b,0,0,N)として呼ぶ
int query(int a,int b,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return inf;
	if(a<=l && r<=b) return dat[k]+ad[k];
	int vl=query(a,b,k*2+1,l,(l+r)/2);
	int vr=query(a,b,k*2+2,(l+r)/2,r);
	return ad[k]+min(vl,vr);
}
//[a,b)に加算する
void add(int a,int b,int x,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return;
	if(a<=l && r<=b) ad[k]+=x;
	else{
		add(a,b,x,k*2+1,l,(l+r)/2);
		add(a,b,x,k*2+2,(l+r)/2,r);
		dat[k]=min(dat[k*2+1]+ad[k*2+1],dat[k*2+2]+ad[k*2+2]);
	}
}
void update(int k,int a){
	k+=N-1;
	dat[k]=a;
	while(k>0){
		k=(k-1)/2;
		dat[k]=min(dat[k*2+1]+ad[k*2+1],dat[k*2+2]+ad[k*2+2]);
	}
	return;
}
//今kにどれくらいの数が加算されているのか
int cal(int k){
	k+=N-1;
	int ret=ad[k];
	while(k>0){
		k=(k-1)/2;ret+=ad[k];
	}
	return ret;
}
int b[200100];
vector<pint> v;
int main()
{
	int n,q,l,r;
	cin>>n;
	rep(i,n) cin>>b[i];
	cin>>q;
	rep(i,q){
		cin>>l>>r;l--;
		v.pb(mp(l,r));
	}
	v.pb(mp(0,0));v.pb(mp(n,n));sort(All(v));
	memset(ad,0,sizeof(ad));
	rep(i,N*2+10) dat[i]=inf;
	update(0,0);
	rep(i,q+1){
		REP(j,v[i].fi,v[i+1].fi){
			if(b[j]==0) add(j+1,n+10,1);
			else add(0,j+1,1);
		}
		if(i>=q) break;
		l=v[i+1].fi;r=v[i+1].se;
		int now=query(0,r+1),su=cal(r);
		update(r,now-su);
	}
	cout<<query(0,n+10)<<endl;
}

```