#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;
#define MAXN 200000
#define INF 0x3f3f3f3f
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define mn(x) t[x]
#define mid ((lef+rig)>>1)
#define rint register int
#define gc() getchar()
inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc())
{
	for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
	for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
	return sgn-'-'?ans:-ans;
}
struct SegmentTree
{
	int t[524289]; void BD(int p, int lef, int rig){lef^rig ? BD(lc(p),lef,mid), BD(rc(p),mid+1,rig), mn(p) = min(mn(lc(p)),mn(rc(p))) : mn(p) = !!lef*INF;}
	void ED(int p, int lef, int rig, int x, int v){lef^rig ? x<=mid ? ED(lc(p),lef,mid,x,v) : ED(rc(p),mid+1,rig,x,v), mn(p) = min(mn(lc(p)),mn(rc(p))) : mn(p) = v;}
	int QU(int p, int lef, int rig, int L, int R){return L^lef||R^rig ? min(L<=mid?QU(lc(p),lef,mid,L,min(mid,R)):INF,R>mid?QU(rc(p),mid+1,rig,max(mid+1,L),R):INF) : mn(p);}
}T[2]; int n, q, c[2][MAXN+5], Ans; struct S{int l,r; S(){} S(int _l, int _r){l=_l,r=_r;}}s[MAXN+5]; inline bool operator < (S a, S b){return a.l^b.l ? a.l<b.l : a.r<b.r;}
int main()
{
	n = read(); for(rint i = 1; i <= n; c[1][i] = c[1][i-1]+read(), c[0][i] = i-c[1][i], i++); Ans = c[1][n];
	q = read(); for(rint i = 1; i <= q; s[i].l = read(), s[i].r = read(), i++); sort(s+1,s+q+1); T[0].BD(1,0,n); T[1].BD(1,0,n);
	for(rint i = 1, f; i <= q; T[0].ED(1,0,n,s[i].r,f-c[0][s[i].r]), T[1].ED(1,0,n,s[i].r,f-c[1][s[i].r]), Ans = min(Ans,f+c[1][n]-c[1][s[i].r]), i++)
		f = min(T[0].QU(1,0,n,s[i].l,s[i].r)+c[0][s[i].r],T[1].QU(1,0,n,0,s[i].l-1)+c[0][s[i].r]-c[0][s[i].l-1]+c[1][s[i].l-1]); printf("%d\n",Ans); return 0;
}
### Prompt

Your task is to create a cpp solution 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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;
#define MAXN 200000
#define INF 0x3f3f3f3f
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define mn(x) t[x]
#define mid ((lef+rig)>>1)
#define rint register int
#define gc() getchar()
inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc())
{
	for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
	for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
	return sgn-'-'?ans:-ans;
}
struct SegmentTree
{
	int t[524289]; void BD(int p, int lef, int rig){lef^rig ? BD(lc(p),lef,mid), BD(rc(p),mid+1,rig), mn(p) = min(mn(lc(p)),mn(rc(p))) : mn(p) = !!lef*INF;}
	void ED(int p, int lef, int rig, int x, int v){lef^rig ? x<=mid ? ED(lc(p),lef,mid,x,v) : ED(rc(p),mid+1,rig,x,v), mn(p) = min(mn(lc(p)),mn(rc(p))) : mn(p) = v;}
	int QU(int p, int lef, int rig, int L, int R){return L^lef||R^rig ? min(L<=mid?QU(lc(p),lef,mid,L,min(mid,R)):INF,R>mid?QU(rc(p),mid+1,rig,max(mid+1,L),R):INF) : mn(p);}
}T[2]; int n, q, c[2][MAXN+5], Ans; struct S{int l,r; S(){} S(int _l, int _r){l=_l,r=_r;}}s[MAXN+5]; inline bool operator < (S a, S b){return a.l^b.l ? a.l<b.l : a.r<b.r;}
int main()
{
	n = read(); for(rint i = 1; i <= n; c[1][i] = c[1][i-1]+read(), c[0][i] = i-c[1][i], i++); Ans = c[1][n];
	q = read(); for(rint i = 1; i <= q; s[i].l = read(), s[i].r = read(), i++); sort(s+1,s+q+1); T[0].BD(1,0,n); T[1].BD(1,0,n);
	for(rint i = 1, f; i <= q; T[0].ED(1,0,n,s[i].r,f-c[0][s[i].r]), T[1].ED(1,0,n,s[i].r,f-c[1][s[i].r]), Ans = min(Ans,f+c[1][n]-c[1][s[i].r]), i++)
		f = min(T[0].QU(1,0,n,s[i].l,s[i].r)+c[0][s[i].r],T[1].QU(1,0,n,0,s[i].l-1)+c[0][s[i].r]-c[0][s[i].l-1]+c[1][s[i].l-1]); printf("%d\n",Ans); return 0;
}
```