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>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 200111

typedef long long ll;
typedef long double ld;

int pre[maxn];
int dp[maxn], b[maxn];
vector<int> v[maxn];

struct segtree{
	int seg[4 * maxn];
	int lazy[4 * maxn];

	void init(){
		memset(seg, 0x3f3f3f3f, sizeof(seg));
		memset(lazy, 0x3f3f3f3f, sizeof(lazy));
	}

	void push(int x, int l, int d){
		seg[x] = min(seg[x], lazy[x]);
		if(l != d){
			lazy[2 * x] = min(lazy[2 * x], lazy[x]);
			lazy[2 * x + 1] = min(lazy[2 * x + 1], lazy[x]);
		}
		lazy[x] = 0x3f3f3f3f;
	}

	void update(int x, int l, int d, int i, int j, int val){
		push(x, l, d);
		if(l > d || l > j || d < i)
			return;

		if(i <= l && d <= j){
			lazy[x] = min(lazy[x], val);
			push(x, l, d);
			return;
		}

		int mid = (l + d) / 2;
		update(2 * x, l, mid, i, j, val);
		update(2 * x + 1, mid + 1, d, i, j, val);
		seg[x] = min(seg[2 * x], seg[2 * x + 1]);
	}

	int query(int x, int l, int d, int i, int j){
		push(x, l, d);
		if(l > d || l > j || d < i)
			return 0x3f3f3f3f;

		if(i <= l && d <= j){
			return seg[x];
		}

		int mid = (l + d) / 2;
		int ret = query(2 * x, l, mid, i, j);
		ret = min(ret, query(2 * x + 1, mid + 1, d, i, j));
	//	seg[x] = min(seg[2 * x], seg[2 * x + 1]);
		return ret;
	}
} seg;

int main(){
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", b + i);
		pre[i] = pre[i - 1] + (!b[i]);
	}

	int q;
	scanf("%d", &q);
	while(q--){
		int l, d;
		scanf("%d%d", &l, &d);
		v[d].pb(l);
	}

	seg.init();
	memset(dp, 0x3f3f3f3f, sizeof(dp));

	dp[0] = 0;
	seg.update(1, 0, n, 0, 0, 0);
	for(int i = 1; i <= n; i++){
		sort(v[i].begin(), v[i].end());

		dp[i] = dp[i - 1] + b[i];
		seg.update(1, 0, n, i, i, dp[i] - pre[i]);

		for(int j : v[i]){
			int cur = seg.query(1, 0, n, j - 1, j - 1) + pre[i];
			dp[i] = min(dp[i], cur);
			seg.update(1, 0, n, j, i, cur - pre[i]);
		}
	}

	printf("%d\n", dp[n]);
	return 0;
}