#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N (1<<18)

int a[(2 * N)];

void init(void){
	f(i, 2 * N)a[i] = -MOD;
	return;
}


void change(int k, int x){
	k += N;
	if (a[k]<x)a[k] = x;
	else return;
	while (k > 1){
		k = k / 2;
		a[k] = max(a[2 * k], a[2 * k + 1]);
	}
	return;
}
//探索(0<=l<r<=n)範囲は(l<=x<r)初期は(l,r,1,0,N)
int max_search(int l, int r, int k, int sl, int sr){
	if (r <= sl || sr <= l)return -MOD;
	else if (l <= sl&&sr <= r) return a[k];
	else{
		int vl = max_search(l, r, 2 * k, sl, (sl + sr) / 2);
		int vr = max_search(l, r, 2 * k + 1, (sl + sr) / 2, sr);
		return max(vl, vr);
	}
}




int main(void){
	int b[N];
	int s[N];
	vector<pair<int, int> >qq;
	int nx = 0;
	int n;
	int m;
	int x, y, z;
	int xx;
	scanf("%d", &n);
	init();
	b[0] = 0;
	s[0] = b[0];
	f(i, n){
		scanf("%d", &x);
		if (x == 0){
			b[i + 1] = b[i] + 1;
			s[i + 1] = b[i + 1];
		}
		else{
			b[i + 1] = b[i];
			s[i + 1] = b[i + 1];
		}
	}
	scanf("%d", &m);
	f(i, m){
		scanf("%d %d", &x, &y);
		qq.push_back(make_pair(x, y));
	}
	sort(qq.begin(), qq.end());
	for (int i = 1; i <= n; i++){
		if (b[i - 1]<b[i]){
			s[i] = max(s[i - 1] + 1, s[i]);
		}
		else s[i] = max(s[i - 1], s[i]);
		if (nx < qq.size()){
			while (qq[nx].first <= i){
				xx = qq[nx].second;
				x = s[i - 1] + (xx - b[xx]) - (i - 1 - b[i - 1]);
				y = max_search(i, xx + 1, 1, 0, N);
				if (y > (-MOD)){
					y += (xx - b[xx]);
					z = max(x, y);
				}
				else z = x;
				s[xx] = max(s[xx], z);
				change(xx, z - (xx - b[xx]));
				nx++;
				if (nx >= qq.size())break;
			}
		}

	}
	printf("%d\n", n-s[n]);

	return 0;

}

### Prompt

Generate a Cpp solution 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<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N (1<<18)

int a[(2 * N)];

void init(void){
	f(i, 2 * N)a[i] = -MOD;
	return;
}


void change(int k, int x){
	k += N;
	if (a[k]<x)a[k] = x;
	else return;
	while (k > 1){
		k = k / 2;
		a[k] = max(a[2 * k], a[2 * k + 1]);
	}
	return;
}
//探索(0<=l<r<=n)範囲は(l<=x<r)初期は(l,r,1,0,N)
int max_search(int l, int r, int k, int sl, int sr){
	if (r <= sl || sr <= l)return -MOD;
	else if (l <= sl&&sr <= r) return a[k];
	else{
		int vl = max_search(l, r, 2 * k, sl, (sl + sr) / 2);
		int vr = max_search(l, r, 2 * k + 1, (sl + sr) / 2, sr);
		return max(vl, vr);
	}
}




int main(void){
	int b[N];
	int s[N];
	vector<pair<int, int> >qq;
	int nx = 0;
	int n;
	int m;
	int x, y, z;
	int xx;
	scanf("%d", &n);
	init();
	b[0] = 0;
	s[0] = b[0];
	f(i, n){
		scanf("%d", &x);
		if (x == 0){
			b[i + 1] = b[i] + 1;
			s[i + 1] = b[i + 1];
		}
		else{
			b[i + 1] = b[i];
			s[i + 1] = b[i + 1];
		}
	}
	scanf("%d", &m);
	f(i, m){
		scanf("%d %d", &x, &y);
		qq.push_back(make_pair(x, y));
	}
	sort(qq.begin(), qq.end());
	for (int i = 1; i <= n; i++){
		if (b[i - 1]<b[i]){
			s[i] = max(s[i - 1] + 1, s[i]);
		}
		else s[i] = max(s[i - 1], s[i]);
		if (nx < qq.size()){
			while (qq[nx].first <= i){
				xx = qq[nx].second;
				x = s[i - 1] + (xx - b[xx]) - (i - 1 - b[i - 1]);
				y = max_search(i, xx + 1, 1, 0, N);
				if (y > (-MOD)){
					y += (xx - b[xx]);
					z = max(x, y);
				}
				else z = x;
				s[xx] = max(s[xx], z);
				change(xx, z - (xx - b[xx]));
				nx++;
				if (nx >= qq.size())break;
			}
		}

	}
	printf("%d\n", n-s[n]);

	return 0;

}

```