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 <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
#define mid ((l+r)>>1)
#define ls (root<<1)
#define rs (root<<1|1)
using namespace std;

int n, q, cnt, b[MAXN], t[MAXN*4];

vector<int> vec[MAXN];

void up(int root)
{
    t[root]=min(t[ls], t[rs]);
}

void build(int root, int l, int r)
{
    if(l==r)
    {
        t[root]=(l?INF:0);
        return;
    }
    build(ls, l, mid);
    build(rs, mid+1, r);
    up(root);
}

void update(int root, int l, int r, int x, int k)
{
    if(l>x || r<x) return;
    if(l==r)
    {
        t[root]=min(t[root], k);
        return;
    }
    update(ls, l, mid, x, k);
    update(rs, mid+1, r, x, k);
    up(root);
}

int query(int root, int l, int r, int x, int y)
{
    if(l>y || r<x) return INF;
    if(l>=x && r<=y) return t[root];
    return min(query(ls, l, mid, x, y), query(rs, mid+1, r, x, y));
}

int main()
{
    scanf("%d", &n);
    for(rint i=1; i<=n; ++i)
    {
        scanf("%d", &b[i]);
        cnt+=(!b[i]);
    }
    scanf("%d", &q);
    for(rint i=1, l, r; i<=q; ++i)
    {
        scanf("%d%d", &l, &r);
        vec[l].push_back(r);
    }
    build(1, 0, n);
    for(rint i=1; i<=n; ++i)
    {
        for(rint j=0; j<vec[i].size(); ++j)
            update(1, 0, n, vec[i][j], query(1, 0, n, i-1, vec[i][j]));
        update(1, 0, n, i, query(1, 0, n, i-1, i-1)+2*b[i]-1);
    }
    printf("%d\n", cnt+query(1, 0, n, n, n));
    return 0;
}