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>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;

const int INF=0x3f3f3f3f;

struct Segtree{
	int N;
	vector<int>dat;
	Segtree(int n){
		N=1;while(N<n)N<<=1;
		dat=vector<int>(2*N,-INF);
	}
	void update(int k,int x){
		k+=N;dat[k]=max(dat[k],x);
		while(k>1){
			k>>=1;
			dat[k]=max(dat[k*2],dat[k*2+1]);
		}
	}
	int query(int l,int r){
		int res=-INF;
		for(l+=N,r+=N;l<r;l>>=1,r>>=1){
			if(l&1)res=max(res,dat[l++]);
			if(r&1)res=max(res,dat[--r]);
		}
		return res;
	}
};

int b[300000];
int sum[300000];
vector<int>E[300000];

int main(){
	int n;cin>>n;
	int cnt=0;
	rep(i,n){
		scanf("%d",&b[i]);
		sum[i+1]+=sum[i];
		if(b[i]==0)sum[i+1]--,cnt++;
		else sum[i+1]++;
	}
	int q;cin>>q;
	rep(i,q){
		int l,r;scanf("%d%d",&l,&r);l--;
		E[l].push_back(r);
	}
	Segtree seg1(n+1),seg2(n+1);
	seg1.update(0,0);seg2.update(0,0);
	int ans=0;
	rep(i,n){
		for(int u:E[i]){
			int s1=seg1.query(0,i)+(sum[u]-sum[i]),s2=seg2.query(i,u)+sum[u];
			int res=max(s1,s2);
			ans=max(ans,res);
			seg1.update(u,res);seg2.update(u,res-sum[u]);
		}
	}
	cout<<n-(cnt+ans)<<endl;
}