#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
#define F first
#define S second
#define INF 1<<19
struct SEG{
	int seg[1<<19];
	SEG(void){for(int i=0;i<1<<19;i++)seg[i]=INF;}
	void up(int a,int x){
		a+=(1<<18)-1;
		seg[a]=min(seg[a],x);
		while(a>0){
			a=(a-1)/2;
			seg[a]=min(seg[a*2+1],seg[a*2+2]);
		}
	}
	int que(int a,int b,int l,int r,int k){
		if(r<a||b<l)return INF;
		if(a<=l&&r<=b)return seg[k];
		return min(que(a,b,l,(l+r-1)/2,k*2+1),que(a,b,(l+r+1)/2,r,k*2+2));
	}
};
int n,q,s[1<<18],l,r,a,o,dp[1<<18],d=INF,e;
P x[1<<18];
SEG p;
int main(void){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
		scanf("%d",&a);
		if(a)s[i]--;
		else s[i]++;
		s[i]+=s[i-1];
		dp[i]=INF;
	}
	scanf("%d",&q);
	for(int i=0;i<q;i++)scanf("%d%d",&x[i].F,&x[i].S);
	sort(x,x+q);
	p.up(0,(n-s[n])/2);
	dp[0]=(n-s[n])/2;
	for(int i=0;i<q;i++){
		l=x[i].F,r=x[i].S;
		while(e<l)d=min(d,dp[e++]);
		o=min(d+s[r]-s[l-1],s[r]+p.que(l,r,0,(1<<18)-1,0));
		p.up(r,o-s[r]);
		dp[r]=o;
	}
	while(e<=n)d=min(d,dp[e++]);
	printf("%d\n",d);
}

### Prompt

Develop a solution in CPP to the problem described below:

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;
typedef pair<int,int> P;
#define F first
#define S second
#define INF 1<<19
struct SEG{
	int seg[1<<19];
	SEG(void){for(int i=0;i<1<<19;i++)seg[i]=INF;}
	void up(int a,int x){
		a+=(1<<18)-1;
		seg[a]=min(seg[a],x);
		while(a>0){
			a=(a-1)/2;
			seg[a]=min(seg[a*2+1],seg[a*2+2]);
		}
	}
	int que(int a,int b,int l,int r,int k){
		if(r<a||b<l)return INF;
		if(a<=l&&r<=b)return seg[k];
		return min(que(a,b,l,(l+r-1)/2,k*2+1),que(a,b,(l+r+1)/2,r,k*2+2));
	}
};
int n,q,s[1<<18],l,r,a,o,dp[1<<18],d=INF,e;
P x[1<<18];
SEG p;
int main(void){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
		scanf("%d",&a);
		if(a)s[i]--;
		else s[i]++;
		s[i]+=s[i-1];
		dp[i]=INF;
	}
	scanf("%d",&q);
	for(int i=0;i<q;i++)scanf("%d%d",&x[i].F,&x[i].S);
	sort(x,x+q);
	p.up(0,(n-s[n])/2);
	dp[0]=(n-s[n])/2;
	for(int i=0;i<q;i++){
		l=x[i].F,r=x[i].S;
		while(e<l)d=min(d,dp[e++]);
		o=min(d+s[r]-s[l-1],s[r]+p.que(l,r,0,(1<<18)-1,0));
		p.up(r,o-s[r]);
		dp[r]=o;
	}
	while(e<=n)d=min(d,dp[e++]);
	printf("%d\n",d);
}

```