#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int ST_MAX = (1 << 21);
const int INF = 1e9 + 7;

template <class T> class ST{
	T x[ST_MAX * 2];
	
	T eval(T a , T b){			//評価
		return min(a,b);
	}
	
	void ren(int a){			//更新
		x[a] = eval(x[2 * a] , x[2 * a + 1]);
		if(a > 0) ren(a / 2);
	}
	
	T read_ST(int a , int b , int e , int s , int f){		//値の取得
		if(e <= s || f <= b) return INF;
		if(s <= b && e <= f) return x[a];
		return eval(read_ST(2 * a , b , (b + e) / 2 , s , f) , read_ST(2 * a + 1 , (b + e) / 2 , e , s , f));
	}
	
public:
	
	ST(){
		fill(x,x+ST_MAX*2,INF);
	}
	
	void put(int a , T b){	//更新の開始
		if(x[a+ST_MAX] <= b) return;
		x[a + ST_MAX] = b;
		ren((a + ST_MAX) / 2);
	}
	
	T get(int s , int f){	//値の取得の開始
		return read_ST(1 , 0 , ST_MAX , s , f);
	}
};

const int MC = 200010;
int N,Q;
int b[MC];
int s[MC];
P2 p[MC];
ST<int> st;

int main(){
	cin >> N;
	repp(i,1,N+1){
		cin >> b[i];
		s[i] = s[i-1] + !b[i];
	}
	cin >> Q;
	repp(i,0,Q){
		cin >> p[i].first >> p[i].second;
	}
	sort(p,p+Q);
	int ans = 0;
	int it = 0;
	repp(i,1,N+1){
		while(it < Q && p[it].first == i){
			int z = st.get(i,p[it].second);
			st.put(p[it].second,min(z,ans+s[N]-s[i-1]));
			//cout << ' ' << p[it].first << ' ' << p[it].second << ' ' << z << ' ' << ans+s[N]-s[i-1] << endl;
			++it;
		}
		ans = min(ans+b[i],st.get(i,i+1)-s[N]+s[i]);
		//cout << i << ' ' << ans << endl;
	}
	cout << ans << endl;
	return 0;
}

### Prompt

Please create a solution in Cpp to the following 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

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int ST_MAX = (1 << 21);
const int INF = 1e9 + 7;

template <class T> class ST{
	T x[ST_MAX * 2];
	
	T eval(T a , T b){			//評価
		return min(a,b);
	}
	
	void ren(int a){			//更新
		x[a] = eval(x[2 * a] , x[2 * a + 1]);
		if(a > 0) ren(a / 2);
	}
	
	T read_ST(int a , int b , int e , int s , int f){		//値の取得
		if(e <= s || f <= b) return INF;
		if(s <= b && e <= f) return x[a];
		return eval(read_ST(2 * a , b , (b + e) / 2 , s , f) , read_ST(2 * a + 1 , (b + e) / 2 , e , s , f));
	}
	
public:
	
	ST(){
		fill(x,x+ST_MAX*2,INF);
	}
	
	void put(int a , T b){	//更新の開始
		if(x[a+ST_MAX] <= b) return;
		x[a + ST_MAX] = b;
		ren((a + ST_MAX) / 2);
	}
	
	T get(int s , int f){	//値の取得の開始
		return read_ST(1 , 0 , ST_MAX , s , f);
	}
};

const int MC = 200010;
int N,Q;
int b[MC];
int s[MC];
P2 p[MC];
ST<int> st;

int main(){
	cin >> N;
	repp(i,1,N+1){
		cin >> b[i];
		s[i] = s[i-1] + !b[i];
	}
	cin >> Q;
	repp(i,0,Q){
		cin >> p[i].first >> p[i].second;
	}
	sort(p,p+Q);
	int ans = 0;
	int it = 0;
	repp(i,1,N+1){
		while(it < Q && p[it].first == i){
			int z = st.get(i,p[it].second);
			st.put(p[it].second,min(z,ans+s[N]-s[i-1]));
			//cout << ' ' << p[it].first << ' ' << p[it].second << ' ' << z << ' ' << ans+s[N]-s[i-1] << endl;
			++it;
		}
		ans = min(ans+b[i],st.get(i,i+1)-s[N]+s[i]);
		//cout << i << ' ' << ans << endl;
	}
	cout << ans << endl;
	return 0;
}

```