#include <bits/stdc++.h>

using namespace std;

struct Min {
	long n;
	Min(long n) :n(n) {}
	operator long() const { return n; }
	void operator+=(const Min &m) { n = min(n, m.n); }
	const Min &operator*(int) const { return *this; }
};
struct seg {
	typedef Min N;
	const N I = 1e9;
	vector<N> t, u;
	seg(int n) :t(n - 1, I), u(n + n - 1, I) {}
	void upd(int a, int b, N n, int p, int q, int l, int r) {
		for (;;) {
			if (b <= l || r <= a)
				break;
			if (a <= l && r <= b) {
				u[q] += n;
				break;
			}
			t[p] += n * (min(b, r) - max(a, l));
			int m = (l + r) / 2;
			upd(a, b, n, p + 1, q + 1, l, m);
			p += m - l;
			q += (m - l) * 2;
			l = m;
		}
	}
	void upd(int a, int b, N n) {
		upd(a, b, n, 0, 0, 0, t.size() + 1);
	}
	N out(int a, int b, int p, int q, int l, int r) const {
		N n = I;
		for (;;) {
			if (b <= l || r <= a)
				break;
			if (a <= l && r <= b) {
				if (l + 1 < r) n += t[p];
				n += u[q] * (r - l);
				break;
			}
			int m = (l + r) / 2;
			n += out(a, b, p + 1, q + 1, l, m);
			p += m - l;
			q += (m - l) * 2;
			l = m;
		}
		return n;
	}
	N out(int a, int b) const {
		return out(a, b, 0, 0, 0, t.size() + 1);
	}
};

int b[222222];
pair<int, int> l[222222];
int main() {
	int n;
	cin >> n;
	int d = n;
	for (int i = 0; i < n; i++)
		scanf("%d", b + i), d -= b[i];
	int q;
	cin >> q;
	for (int i = 0; i < q; i++)
		scanf("%d%d", &l[i].first, &l[i].second);
	sort(l, l + q);
	l[q].first = n + 1;
	seg s(n + 1);
	s.upd(0, 1, d);
	int p = 1;
	for (int i = 0;; i++) {
		for (; p < l[i].first; p++)
			s.upd(p, p + 1, s.out(p - 1, p) + b[p - 1] * 2 - 1);
		if (i == q) break;
		s.upd(l[i].second, l[i].second + 1, s.out(p - 1, l[i].second));
	}
	cout << s.out(n, n + 1) << 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;

struct Min {
	long n;
	Min(long n) :n(n) {}
	operator long() const { return n; }
	void operator+=(const Min &m) { n = min(n, m.n); }
	const Min &operator*(int) const { return *this; }
};
struct seg {
	typedef Min N;
	const N I = 1e9;
	vector<N> t, u;
	seg(int n) :t(n - 1, I), u(n + n - 1, I) {}
	void upd(int a, int b, N n, int p, int q, int l, int r) {
		for (;;) {
			if (b <= l || r <= a)
				break;
			if (a <= l && r <= b) {
				u[q] += n;
				break;
			}
			t[p] += n * (min(b, r) - max(a, l));
			int m = (l + r) / 2;
			upd(a, b, n, p + 1, q + 1, l, m);
			p += m - l;
			q += (m - l) * 2;
			l = m;
		}
	}
	void upd(int a, int b, N n) {
		upd(a, b, n, 0, 0, 0, t.size() + 1);
	}
	N out(int a, int b, int p, int q, int l, int r) const {
		N n = I;
		for (;;) {
			if (b <= l || r <= a)
				break;
			if (a <= l && r <= b) {
				if (l + 1 < r) n += t[p];
				n += u[q] * (r - l);
				break;
			}
			int m = (l + r) / 2;
			n += out(a, b, p + 1, q + 1, l, m);
			p += m - l;
			q += (m - l) * 2;
			l = m;
		}
		return n;
	}
	N out(int a, int b) const {
		return out(a, b, 0, 0, 0, t.size() + 1);
	}
};

int b[222222];
pair<int, int> l[222222];
int main() {
	int n;
	cin >> n;
	int d = n;
	for (int i = 0; i < n; i++)
		scanf("%d", b + i), d -= b[i];
	int q;
	cin >> q;
	for (int i = 0; i < q; i++)
		scanf("%d%d", &l[i].first, &l[i].second);
	sort(l, l + q);
	l[q].first = n + 1;
	seg s(n + 1);
	s.upd(0, 1, d);
	int p = 1;
	for (int i = 0;; i++) {
		for (; p < l[i].first; p++)
			s.upd(p, p + 1, s.out(p - 1, p) + b[p - 1] * 2 - 1);
		if (i == q) break;
		s.upd(l[i].second, l[i].second + 1, s.out(p - 1, l[i].second));
	}
	cout << s.out(n, n + 1) << endl;
	return 0;
}

```