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;
template<class T> inline bool chkmax(T& a,T b){ return a<b?a=b,1:0; }
template<class T> inline bool chkmin(T& a,T b){ return a>b?a=b,1:0; }
template<typename T> inline T& read(T& x){
    static char c; bool flag=0;
    while(!isdigit(c=getchar())) if(c=='-') flag=1;
    for(x=c-'0';isdigit(c=getchar());(x*=10)+=c-'0');
    if(flag) x=-x;
    return x;
}
const int maxn=200010,INF=0x3f3f3f3f;
int n,q,a[maxn],s[maxn],f[maxn],ans;
struct data{
    int l,r;
    bool operator < (const data& rhs) const{
        return l<rhs.l;
    }
} t[maxn];
namespace SGT{
#define ls h<<1
#define rs h<<1|1
#define mid ((l+r)>>1)
#define lc l,mid
#define rc mid+1,r
    int T[maxn*3][2];
    void creat(){ memset(T,INF,sizeof T); }
    void pushup(int h){
        T[h][0]=min(T[ls][0],T[rs][0]);
        T[h][1]=min(T[ls][1],T[rs][1]);
    }
    void update(int h,int l,int r,int p,int w,int op){
        if(l==r) return void(chkmin(T[h][op],w));
        if(p<=mid) update(ls,lc,p,w,op);
        else update(rs,rc,p,w,op);
        pushup(h);
    }
    int query(int h,int l,int r,int L,int R,int op){
        if(L>R) return INF;
        if(L<=l&&r<=R) return T[h][op];
        int res=INF;
        if(L<=mid) chkmin(res,query(ls,lc,L,R,op));
        if(R>mid) chkmin(res,query(rs,rc,L,R,op));
        return res;
    }
}
using namespace SGT;
int main(){
    read(n);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+read(a[i]);
    read(q);
    for(int i=1;i<=q;i++) read(t[i].l),read(t[i].r);
    sort(t+1,t+q+1);
    creat();
    f[0]=s[n];
    for(int i=1;i<=q;i++){
        f[i]=s[n]+(t[i].r-t[i].l+1)-(s[t[i].r]-s[t[i].l-1])*2;
        chkmin(f[i],query(1,1,n,1,t[i].l-1,0)+(t[i].r-t[i].l+1)-2*(s[t[i].r]-s[t[i].l-1]));
        chkmin(f[i],query(1,1,n,t[i].l,t[i].r-1,1)+t[i].r-2*s[t[i].r]);
        update(1,1,n,t[i].r,f[i],0);
        update(1,1,n,t[i].r,f[i]-t[i].r+2*s[t[i].r],1);
    }
    ans=INF;
    for(int i=0;i<=q;i++) chkmin(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}