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<iostream>
#include<algorithm>
#include<vector>
using namespace std;

#define sz(x) (int)(x.size())
#define fi(a,b) for(int i=a;i<b;++i)
#define fj(a,b) for(int j=a;j<b;++j)
#define fdi(a,b) for(int i=a-1;i>=b;--i)
#define pb push_back
//////////////////

int const INF = 1e9 + 41;
int const N = 2e5 + 41;
int n, b[N], qu, l[N], r[N], ans;

void remin(int &a, int b){
	a = min(a, b);
}

namespace tree{
	int t[(1 << 19)], l, r, val, p;
	
	void build(int v, int tl, int tr){
		if(tl == tr){
			t[v] = INF;
		}else{
			int tm = (tl+tr)/2;
			build(v*2+1, tl, tm);
			build(v*2+2, tm+1, tr);
			t[v] = min(t[v*2+1], t[v*2+2]);
		}
	}

	void build(){
		build(0, 0, n-1);
	}

	void upd(int v, int tl, int tr){
		if(tl == tr){
			remin(t[v], val);
		}else{
			int tm = (tl+tr)/2;
			if(p <= tm) upd(v*2+1, tl, tm);
			else upd(v*2+2, tm+1, tr);
			t[v] = min(t[v*2+1], t[v*2+2]);
		}
	}

	void upd(int p, int val){
		tree::p = p;
		tree::val = val;
		upd(0, 0, n-1);
	}
	
	int ask(int v, int tl, int tr){
		if(l > tr || tl > r) return INF;
		if(l <= tl && tr <= r) return t[v];
		int tm = (tl+tr)/2;
		return min(ask(v*2+1, tl, tm), ask(v*2+2, tm+1, tr));
	}

	int ask(int l, int r){
		tree::l = l;
		tree::r = r;
		return ask(0, 0, n-1);
	}
};

vector<int> e[N];

void solve(){
	tree::build();
	fi(0, qu) e[l[i]].pb(r[i]);
	int v0 = 0;
	fi(0, n){
		fj(0, sz(e[i])){
			int r = e[i][j];
			int v1 = tree::ask(i, r-1);
			int v = min(v1, v0);
			tree::upd(r, v);
		}
		v0 += (b[i] == 1 ? 1 : -1);
		v0 = min(v0, tree::ask(i, i));
	}
	ans = v0;
	fi(0, n) if(b[i] == 0) ++ans;
}

int main(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif

	scanf("%d",&n);
	fi(0, n) scanf("%d",&b[i]);
	scanf("%d",&qu);
	fi(0, qu){
		scanf("%d %d",&l[i],&r[i]);
		--l[i];
		--r[i];
	}

	solve();

	printf("%d\n",ans);

	return 0;
}