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

Solution (in CPP):

Solution:
#include"bits/stdc++.h"
using namespace std;

#define MAX 200002

int n;

vector<int> vv;

long long int seg[MAX*4];
long long int laz[MAX*4];

void upd(int b){
	if(b*2+2<MAX*4){
		laz[b*2+1]+=laz[b];
		laz[b*2+2]+=laz[b];
	}
	seg[b]+=laz[b];
	laz[b]=0;
}

inline long long int query(int b,int l,int r,int ll,int rr){
	upd(b);
	if(r<=ll||rr<=l)return INT_MAX;
	if(ll<=l&&r<=rr)return seg[b];
	return min(query(b*2+1,l,(l+r)>>1,ll,rr),query(b*2+2,(l+r)>>1,r,ll,rr));
}

int dp[MAX];

vector<int> v[MAX];


inline void add(int b,int l,int r,int ll,int rr,int x){
	upd(b);
	if(r<=ll||rr<=l)return;
	if(ll<=l&&r<=rr){
		laz[b]+=x;
		upd(b);
		return;
	}
	add(b*2+1,l,(l+r)>>1,ll,rr,x);
	add(b*2+2,(l+r)>>1,r,ll,rr,x);
	seg[b]=max(seg[b*2+1],seg[b*2+2]);
}
inline void chang(int b,int l,int r,int ll,long long int x){
	upd(b);
	if(l<=ll&&ll<r){
		if(l+1==r){
			seg[b]=min(seg[b],x);
			return;
		}
		chang(b*2+1,l,(l+r)>>1,ll,x);
		chang(b*2+2,(l+r)>>1,r,ll,x);
		seg[b]=min(seg[b*2+1],seg[b*2+2]);
	}
}
int q;
int main(){
	for(int i=0;i<MAX*4;i++)seg[i]=INT_MAX;
	cin>>n;
	for(int i=0;i<n;i++){
		int a;
		scanf("%d",&a);
		vv.push_back(a);
	}
	cin>>q;
	for(int i=0;i<q;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		a--;
		b--;
		v[a].push_back(b);
	}
	for(int i=0;i<=n;i++){
		dp[i]=INT_MAX;
	}
	dp[0]=0;
	for(int i=0;i<=n;i++){
		chang(0,0,n+1,i,dp[i]);
		dp[i]=query(0,0,n+1,i,i+1);
		if(i==n)break;
		for(int el:v[i]){
			chang(0,0,n+1,el+1,query(0,0,n+1,i,el+1));
		}
		if(vv[i]==0){
			add(0,0,n+1,i,n+1,1);
		}
		dp[i+1]=dp[i];
		if(vv[i]==1)dp[i+1]++;
	}
	printf("%lld\n",dp[n]);
	return 0;
}