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>

const int maxn=2e5+10;

int n,m,cnt;
int F[maxn];
int cost[maxn];
std::vector<int> right[maxn];

int minv[maxn<<2];
int get(int r,int L,int R,int Lu,int Ru){
	if (L>Ru||R<Lu)return 0x3F3F3F3F;
	if (L>=Lu&&R<=Ru)return minv[r];
	int Mid=(L+R)>>1;
	return std::min(get(r<<1,L,Mid,Lu,Ru),get(r<<1|1,Mid+1,R,Lu,Ru));
}

void insert(int r,int L,int R,int p,int v){
	if (L==R)return minv[r]=v,void();
	int Mid=(L+R)>>1;
	if (p<=Mid)insert(r<<1,L,Mid,p,v);
	else insert(r<<1|1,Mid+1,R,p,v);
	minv[r]=std::min(minv[r<<1],minv[r<<1|1]);
}

int main (){
#ifdef LOCAL
	freopen("input","r",stdin);
#endif
	std::cin >> n;
	for (int i=1,x;i<=n;i++){
		std::cin >> x;
		cnt+=(x==0);
		cost[i]=x>0?1:-1;
	}
	std::cin >> m;
	for (int i=1,L,R;i<=m;i++){
		std::cin >> L >> R;
		right[L].push_back(R);
	}
	memset(F,0x3F,sizeof(F));
	memset(minv,0x3F,sizeof(minv));
	F[0]=0;
	for (int i=1,tmp;i<=n;i++){
		F[i]=std::min(F[i],F[i-1]+cost[i]);
		for (int R:right[i]){
			tmp=std::min(F[i-1],get(1,1,n,std::max(i-1,1),R));
			if (tmp<F[R])
				insert(1,1,n,R,F[R]=tmp);
		}
	}
	std::cout << F[n]+cnt << '\n';
	return 0;
}