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 "cstdio"
# include "iostream"
# include "algorithm"
# define LC (x<<1)
# define RC (x<<1|1)

using namespace std;

const int maxm=2e5+10;
const int Inf=0x3f3f3f3f;

int N,Q,B[maxm],Delta[maxm];

struct Segment_Tree{
    int Left;
    int Right;
    int Lazy;
    int Max;
    # define Left(x) Tree[x][Kind].Left
    # define Right(x) Tree[x][Kind].Right
	# define Max(x) Tree[x][Kind].Max
}Tree[maxm<<2][2];

struct segment{
	int Left;
	int Right;
	# define L(x) Segment[x].Left
	# define R(x) Segment[x].Right
}Segment[maxm];

inline void Update(int x,int Kind){
	Max(x)=max(Max(LC),Max(RC));
	return;
}

void Build(int x,int l,int r,int Kind){
    Left(x)=l,Right(x)=r;
    if(l==r){
    	if(l!=0) Max(x)=-Inf;
		return;
	}
	int Mid=(l+r)>>1;
	Build(LC,l,Mid,Kind);
	Build(RC,Mid+1,r,Kind);
    Update(x,Kind);
	return;
}

void Change(int x,int y,int Val,int Kind){
	if(Left(x)==Right(x)){
        Max(x)=Val;
        return;
	}
	int Mid=(Left(x)+Right(x))>>1;
	if(y<=Mid) Change(LC,y,Val,Kind);
	else Change(RC,y,Val,Kind);
	Update(x,Kind);
	return;
}

int Ask(int x,int l,int r,int Kind){
	if(l<=Left(x) && r>=Right(x)){
		return Max(x);
	}
	int Mid=(Left(x)+Right(x))>>1;
	int Result=-Inf;
	if(l<=Mid) Result=Ask(LC,l,r,Kind);
	if(r>Mid) Result=max(Result,Ask(RC,l,r,Kind));
	return Result;
}

inline bool Comp(segment a,segment b){return a.Left==b.Left?a.Right<b.Right:a.Left<b.Left;}

int main(){
	register int i,Ans=0,Add=0,Result=0;
	scanf("%d",&N);
	for(i=1;i<=N;i++){
		scanf("%d",B+i);
		Delta[i]=Delta[i-1]+(B[i]==1?1:-1);
		Ans+=(B[i]==0);
	}
	Build(1,0,N,0);
	Build(1,0,N,1);
	scanf("%d",&Q);
	for(i=1;i<=Q;i++) scanf("%d%d",&L(i),&R(i));
	sort(Segment+1,Segment+1+Q,Comp);
	for(i=1;i<=Q;i++){
		Add=Delta[R(i)]-Delta[L(i)-1]+Ask(1,0,L(i)-1,0);
		Add=max(Add,Delta[R(i)]+Ask(1,L(i),R(i),1));
		Change(1,R(i),Add,0);
		Change(1,R(i),Add-Delta[R(i)],1);
		Result=max(Result,Add);
  	}
	cout<<N-(Ans+Result);
	return 0;
}