#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int inf = 1145141919;
struct seg
{
	vector<int> t;
	seg(int n) :t(n * 2 - 1, inf) {}
	bool add(int p, int n, int o, int l, int r)
	{
		if (l + 1 == r) {
			if (n >= t[o])
				return true;
			t[o] = n;
			return false;
		}
		int m = (l + r) / 2;
		if ((p < m ? add(p, n, o + 1, l, m) : add(p, n, o + (m - l) * 2, m, r)) || n >= t[o])
			return true;
		t[o] = n;
		return false;
	}
	int min(int a, int b, int o, int l, int r)
	{
		if (a >= b || a >= r || b <= l)
			return inf;
		if (a <= l && b >= r)
			return t[o];
		int m = (l + r) / 2;
		int p = min(a, b, o + 1, l, m);
		int q = min(a, b, o + (m - l) * 2, m, r);
		return p < q ? p : q;
	}
};

int main()
{
	int N, Q, b;
	cin >> N;
	vector<int> c(N + 1);
	for (int i = 0; i < N; i++) {
		cin >> b;
		c[i + 1] = c[i] + b * 2 - 1;
	}
	cin >> Q;
	vector<pair<int, int>> s(Q);
	while (Q--)
		cin >> s[Q].first >> s[Q].second;
	sort(s.begin(), s.end());
	seg s0(N + 1), s1(N + 1);
	s0.add(0, (N + c[N]) / 2, 0, 0, N + 1);
	s1.add(0, (N - c[N]) / 2, 0, 0, N + 1);
	int r = 0;
	for (auto lr : s) {
		int m0 = s0.min(0, lr.first, 0, 0, N + 1) + c[lr.first - 1] - c[lr.second];
		r = lr.second;
		int m1 = s1.min(lr.first, r, 0, 0, N + 1) - c[r] + c[N];
		if (m0 > m1) m0 = m1;
		s0.add(r, m0, 0, 0, N + 1);
		s1.add(r, m0 + c[r] - c[N], 0, 0, N + 1);
	}
	cout << s0.t[0] << 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 <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int inf = 1145141919;
struct seg
{
	vector<int> t;
	seg(int n) :t(n * 2 - 1, inf) {}
	bool add(int p, int n, int o, int l, int r)
	{
		if (l + 1 == r) {
			if (n >= t[o])
				return true;
			t[o] = n;
			return false;
		}
		int m = (l + r) / 2;
		if ((p < m ? add(p, n, o + 1, l, m) : add(p, n, o + (m - l) * 2, m, r)) || n >= t[o])
			return true;
		t[o] = n;
		return false;
	}
	int min(int a, int b, int o, int l, int r)
	{
		if (a >= b || a >= r || b <= l)
			return inf;
		if (a <= l && b >= r)
			return t[o];
		int m = (l + r) / 2;
		int p = min(a, b, o + 1, l, m);
		int q = min(a, b, o + (m - l) * 2, m, r);
		return p < q ? p : q;
	}
};

int main()
{
	int N, Q, b;
	cin >> N;
	vector<int> c(N + 1);
	for (int i = 0; i < N; i++) {
		cin >> b;
		c[i + 1] = c[i] + b * 2 - 1;
	}
	cin >> Q;
	vector<pair<int, int>> s(Q);
	while (Q--)
		cin >> s[Q].first >> s[Q].second;
	sort(s.begin(), s.end());
	seg s0(N + 1), s1(N + 1);
	s0.add(0, (N + c[N]) / 2, 0, 0, N + 1);
	s1.add(0, (N - c[N]) / 2, 0, 0, N + 1);
	int r = 0;
	for (auto lr : s) {
		int m0 = s0.min(0, lr.first, 0, 0, N + 1) + c[lr.first - 1] - c[lr.second];
		r = lr.second;
		int m1 = s1.min(lr.first, r, 0, 0, N + 1) - c[r] + c[N];
		if (m0 > m1) m0 = m1;
		s0.add(r, m0, 0, 0, N + 1);
		s1.add(r, m0 + c[r] - c[N], 0, 0, N + 1);
	}
	cout << s0.t[0] << endl;
	return 0;
}

```