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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define EB emplace_back

typedef std::vector <int> vector;
const int N = 200054;

int n, m;
int b[N];
vector ri[N];

inline void down(int &x, const int y) {x > y ? x = y : 0;}
inline int min(const int x, const int y) {return x < y ? x : y;}

namespace ST {
	#define segc int M = (L + R - 1) >> 1, lc = id << 1, rc = lc | 1
	int x[N * 4], *val[N];

	void build(int id, int L, int R) {
		x[id] = INT_MAX;
		if (L == R) {val[L] = x + id; return;}
		segc; build(lc, L, M), build(rc, M + 1, R);
	}

	void adj(int id, int L, int R, int h, int v) {
		if (L == R) {x[id] = v; return;}
		segc; h <= M ? adj(lc, L, M, h, v) : adj(rc, M + 1, R, h, v);
		x[id] = min(x[lc], x[rc]);
	}

	int range(int id, int L, int R, int ql, int qr) {
		if (ql <= L && R <= qr) return x[id];
		segc, s = INT_MAX;
		if (ql <= M) down(s, range(lc, L, M, ql, qr));
		if (qr > M) down(s, range(rc, M + 1, R, ql, qr));
		return s;
	}
}

int main() {
	int i, l, r, ans = 0;
	scanf("%d", &n);
	for (i = 1; i <= n; ++i) scanf("%d", b + i), ans += !b[i];
	scanf("%d", &m);
	for (i = 0; i < m; ++i) scanf("%d%d", &l, &r), ri[l].EB(r);
	ST::build(1, 0, n), ST::adj(1, 0, n, 0, 0);
	for (i = 1; i <= n; ++i) {
		for (int r : ri[i]) ST::adj(1, 0, n, r, ST::range(1, 0, n, i - 1, r));
		if ((l = *ST::val[i - 1] + (b[i] ? 1 : -1)) < *ST::val[i])
			ST::adj(1, 0, n, i, l);
	}
	printf("%d\n", ans + *ST::val[n]);
	return 0;
}