#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <iomanip>
#include <algorithm>
using namespace std;

typedef pair <int, int> ii;

const int Maxn = 200005;
const int Maxm = 1048576;
const int Inf = 1000000000;

int n;
int b[Maxn];
int cnt[Maxn];
int q;
ii seq[Maxn];
int dp[Maxn];
int st[Maxm];

int Get(int l, int r) { return cnt[r] - cnt[l - 1]; }

void Clear(int v, int l, int r)
{
	st[v] = Inf;
	if (l < r) {
		int m = l + r >> 1;
		Clear(2 * v, l, m); 
		Clear(2 * v + 1, m + 1, r);
	}
}

int Get(int v, int l, int r, int x)
{
	int res = st[v] - Get(x, r);
	if (l < r) {
		int m = l + r >> 1;
		if (x <= m) res = min(res, Get(2 * v, l, m, x));
		else res = min(res, Get(2 * v + 1, m + 1, r, x));
	}
	return res;
}

void Insert(int v, int l, int r, int a, int b, int val)
{
	if (l == a && r == b) st[v] = min(st[v], val);
	else {
		int m = l + r >> 1;
		if (b <= m) Insert(2 * v, l, m, a, b, val);
		else if (m + 1 <= a) Insert(2 * v + 1, m + 1, r, a, b, val);
		else {
			Insert(2 * v, l, m, a, m, val - Get(m + 1, b));
			Insert(2 * v + 1, m + 1, r, m + 1, b, val);
		}
	} 
}

bool Less(const ii &a, const ii &b)
{
	return a.second < b.second;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &b[i]);
		cnt[i] = cnt[i - 1] + (b[i] == 0);
	}
	Clear(1, 1, n);
	scanf("%d", &q);
	for (int i = 0; i < q; i++)
		scanf("%d %d", &seq[i].first, &seq[i].second);
	sort(seq, seq + q, Less);
	int pnt = 0;
	dp[1] = 0;
	for (int i = 2; i <= n + 1; i++) {
		dp[i] = dp[i - 1] + (b[i - 1] == 1);
		while (pnt < q && seq[pnt].second + 1 == i) {
			int cand = min(dp[seq[pnt].first], Get(1, 1, n, seq[pnt].first)) + Get(seq[pnt].first, seq[pnt].second);
			Insert(1, 1, n, seq[pnt].first, seq[pnt].second, cand);
			dp[i] = min(dp[i], cand);
			pnt++;
		}
	}
	printf("%d\n", dp[n + 1]);
	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 <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <iomanip>
#include <algorithm>
using namespace std;

typedef pair <int, int> ii;

const int Maxn = 200005;
const int Maxm = 1048576;
const int Inf = 1000000000;

int n;
int b[Maxn];
int cnt[Maxn];
int q;
ii seq[Maxn];
int dp[Maxn];
int st[Maxm];

int Get(int l, int r) { return cnt[r] - cnt[l - 1]; }

void Clear(int v, int l, int r)
{
	st[v] = Inf;
	if (l < r) {
		int m = l + r >> 1;
		Clear(2 * v, l, m); 
		Clear(2 * v + 1, m + 1, r);
	}
}

int Get(int v, int l, int r, int x)
{
	int res = st[v] - Get(x, r);
	if (l < r) {
		int m = l + r >> 1;
		if (x <= m) res = min(res, Get(2 * v, l, m, x));
		else res = min(res, Get(2 * v + 1, m + 1, r, x));
	}
	return res;
}

void Insert(int v, int l, int r, int a, int b, int val)
{
	if (l == a && r == b) st[v] = min(st[v], val);
	else {
		int m = l + r >> 1;
		if (b <= m) Insert(2 * v, l, m, a, b, val);
		else if (m + 1 <= a) Insert(2 * v + 1, m + 1, r, a, b, val);
		else {
			Insert(2 * v, l, m, a, m, val - Get(m + 1, b));
			Insert(2 * v + 1, m + 1, r, m + 1, b, val);
		}
	} 
}

bool Less(const ii &a, const ii &b)
{
	return a.second < b.second;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &b[i]);
		cnt[i] = cnt[i - 1] + (b[i] == 0);
	}
	Clear(1, 1, n);
	scanf("%d", &q);
	for (int i = 0; i < q; i++)
		scanf("%d %d", &seq[i].first, &seq[i].second);
	sort(seq, seq + q, Less);
	int pnt = 0;
	dp[1] = 0;
	for (int i = 2; i <= n + 1; i++) {
		dp[i] = dp[i - 1] + (b[i - 1] == 1);
		while (pnt < q && seq[pnt].second + 1 == i) {
			int cand = min(dp[seq[pnt].first], Get(1, 1, n, seq[pnt].first)) + Get(seq[pnt].first, seq[pnt].second);
			Insert(1, 1, n, seq[pnt].first, seq[pnt].second, cand);
			dp[i] = min(dp[i], cand);
			pnt++;
		}
	}
	printf("%d\n", dp[n + 1]);
	return 0;
}
```