#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

namespace io
{
	const int maxb = 1 << 15;
	char b[maxb], *s = b, *t = b;
	bool Getchar(char &ch)
	{
		return ch = s == t && (t = (s = b) + fread(b, 1, maxb, stdin)) == b ? 0 : *s ++;
	}
	int Getint()
	{
		char ch;
		while (Getchar(ch) && (ch < '0' || ch > '9'));
		int s = ch - '0';
		while (Getchar(ch) && ch >= '0' && ch <= '9')
			s = s * 10 + ch - '0';
		return s;
	}
}

using io::Getint;

template<typename ty> bool Chkmax(ty &x, const ty &y) { return x < y ? x = y, 1 : 0; }
template<typename ty> bool Chkmin(ty &x, const ty &y) { return x > y ? x = y, 1 : 0; }

const int maxn = 2e5 + 10;
const int inf = 1e9 + 10;

int M, Mn[maxn * 4];

void Init(int n)
{
	for (M = 1; M < (n + 2); M <<= 1);
	for (int i = M + M; i; -- i) Mn[i] = inf;
}

void Modify(int t, int val)
{
	for (t += M; t; t >>= 1) Chkmin(Mn[t], val);
}

int Query(int s, int t)
{
	int res = inf;
	for (s += M - 1, t += M + 1; s ^ t ^ 1; s >>= 1, t >>= 1)
	{
		if (~ s & 1) Chkmin(res, Mn[s ^ 1]);
		if (  t & 1) Chkmin(res, Mn[t ^ 1]);
	}
	return res;
}

bool b[maxn];
vector<int> opt[maxn];
int f[maxn];

int main()
{
	int n = Getint(), ans = 0;
	for (int i = 1; i <= n; ++ i)
	{
		b[i] = Getint();
		ans += !b[i];
	}
	int Q = Getint();
	for (int i = 1; i <= Q; ++ i)
	{
		int l = Getint(), r = Getint();
		opt[l].push_back(r);
	}
	Init(n);
	for (int i = 0; i <= n; ++ i)
	{
		if (i) f[i] = min(f[i - 1] + (b[i] ? 1 : -1), Query(i, i));
		int size = opt[i + 1].size();
		sort(opt[i + 1].begin(), opt[i + 1].end());
		for (int j = size - 1; ~ j; -- j)
			Modify(opt[i + 1][j], min(Query(i + 1, opt[i + 1][j]), f[i]));
	}
	ans += f[n];
	printf("%d\n", ans);
	return 0;
}

### Prompt

In CPP, your task is to solve 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 <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

namespace io
{
	const int maxb = 1 << 15;
	char b[maxb], *s = b, *t = b;
	bool Getchar(char &ch)
	{
		return ch = s == t && (t = (s = b) + fread(b, 1, maxb, stdin)) == b ? 0 : *s ++;
	}
	int Getint()
	{
		char ch;
		while (Getchar(ch) && (ch < '0' || ch > '9'));
		int s = ch - '0';
		while (Getchar(ch) && ch >= '0' && ch <= '9')
			s = s * 10 + ch - '0';
		return s;
	}
}

using io::Getint;

template<typename ty> bool Chkmax(ty &x, const ty &y) { return x < y ? x = y, 1 : 0; }
template<typename ty> bool Chkmin(ty &x, const ty &y) { return x > y ? x = y, 1 : 0; }

const int maxn = 2e5 + 10;
const int inf = 1e9 + 10;

int M, Mn[maxn * 4];

void Init(int n)
{
	for (M = 1; M < (n + 2); M <<= 1);
	for (int i = M + M; i; -- i) Mn[i] = inf;
}

void Modify(int t, int val)
{
	for (t += M; t; t >>= 1) Chkmin(Mn[t], val);
}

int Query(int s, int t)
{
	int res = inf;
	for (s += M - 1, t += M + 1; s ^ t ^ 1; s >>= 1, t >>= 1)
	{
		if (~ s & 1) Chkmin(res, Mn[s ^ 1]);
		if (  t & 1) Chkmin(res, Mn[t ^ 1]);
	}
	return res;
}

bool b[maxn];
vector<int> opt[maxn];
int f[maxn];

int main()
{
	int n = Getint(), ans = 0;
	for (int i = 1; i <= n; ++ i)
	{
		b[i] = Getint();
		ans += !b[i];
	}
	int Q = Getint();
	for (int i = 1; i <= Q; ++ i)
	{
		int l = Getint(), r = Getint();
		opt[l].push_back(r);
	}
	Init(n);
	for (int i = 0; i <= n; ++ i)
	{
		if (i) f[i] = min(f[i - 1] + (b[i] ? 1 : -1), Query(i, i));
		int size = opt[i + 1].size();
		sort(opt[i + 1].begin(), opt[i + 1].end());
		for (int j = size - 1; ~ j; -- j)
			Modify(opt[i + 1][j], min(Query(i + 1, opt[i + 1][j]), f[i]));
	}
	ans += f[n];
	printf("%d\n", ans);
	return 0;
}

```