#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e18

struct RangeMinQuery{
  ll dat[(1<<20)-1];
  int size;

  void init(int n_){
    size=1;
    while(size<n_) size*=2;
    for(int i=0;i<2*size-1;i++)dat[i]=INF;
  }

  void update(int k,ll a){
    k+=size-1;
    dat[k]=a;
    while(k>0){
      k=(k-1)/2;
      dat[k]=min(dat[k*2+1],dat[k*2+2]);
    }
  }

  ll subquery(int a,int b,int k,int l,int r){
    if(r<=a||b<=l)return INF;
    if(a<=l&&r<=b)return dat[k];
    else{
      return min(subquery(a,b,k*2+1,l,(l+r)/2),subquery(a,b,k*2+2,(l+r)/2,r));
    }
  }
  
  ll query(int a,int b){
    return subquery(a,b,0,0,size);
  }
};

ll n;
ll b[201010];
ll cnt[2][201010];
ll f[201010];
ll q;
RangeMinQuery dp,dp2;
vector<P> ps; 

int main(){
	cin>>n;
  rep(i,n)cin>>b[i];
  rep(i,n){
    cnt[b[i]][i+1]++;
  }
  rep(j,2)rep(i,n)cnt[j][i+1]+=cnt[j][i];
  cin>>q;
  rep(i,q){
    ll l,r;
    cin>>l>>r;
    l--;
    ps.push_back(P(l,r));
  }
  sort(all(ps));
  rep(i,n+1)f[i]=cnt[0][i]-cnt[1][i];
  dp.init(n+1); dp2.init(n+1);
  dp.update(0,cnt[1][n]);
  dp2.update(0,dp.query(0,1)-f[0]);
  for(P p : ps){
    ll l=p.fi,r=p.se;
    ll crt=INF;
    minch(crt,dp.query(0,l+1)+(cnt[0][r]-cnt[0][l])-(cnt[1][r]-cnt[1][l]));
    minch(crt,dp2.query(l+1,r)+(cnt[0][r]-cnt[1][r]));
    ll pre=dp.query(r,r+1);
    if(crt<pre) dp.update(r,crt);
    pre=dp2.query(r,r+1);
    if(crt-f[r]<pre) dp2.update(r,crt-f[r]);
  }
  cout<<dp.query(0,n+1)<<endl;
	return 0;
}

### Prompt

Please formulate 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 <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e18

struct RangeMinQuery{
  ll dat[(1<<20)-1];
  int size;

  void init(int n_){
    size=1;
    while(size<n_) size*=2;
    for(int i=0;i<2*size-1;i++)dat[i]=INF;
  }

  void update(int k,ll a){
    k+=size-1;
    dat[k]=a;
    while(k>0){
      k=(k-1)/2;
      dat[k]=min(dat[k*2+1],dat[k*2+2]);
    }
  }

  ll subquery(int a,int b,int k,int l,int r){
    if(r<=a||b<=l)return INF;
    if(a<=l&&r<=b)return dat[k];
    else{
      return min(subquery(a,b,k*2+1,l,(l+r)/2),subquery(a,b,k*2+2,(l+r)/2,r));
    }
  }
  
  ll query(int a,int b){
    return subquery(a,b,0,0,size);
  }
};

ll n;
ll b[201010];
ll cnt[2][201010];
ll f[201010];
ll q;
RangeMinQuery dp,dp2;
vector<P> ps; 

int main(){
	cin>>n;
  rep(i,n)cin>>b[i];
  rep(i,n){
    cnt[b[i]][i+1]++;
  }
  rep(j,2)rep(i,n)cnt[j][i+1]+=cnt[j][i];
  cin>>q;
  rep(i,q){
    ll l,r;
    cin>>l>>r;
    l--;
    ps.push_back(P(l,r));
  }
  sort(all(ps));
  rep(i,n+1)f[i]=cnt[0][i]-cnt[1][i];
  dp.init(n+1); dp2.init(n+1);
  dp.update(0,cnt[1][n]);
  dp2.update(0,dp.query(0,1)-f[0]);
  for(P p : ps){
    ll l=p.fi,r=p.se;
    ll crt=INF;
    minch(crt,dp.query(0,l+1)+(cnt[0][r]-cnt[0][l])-(cnt[1][r]-cnt[1][l]));
    minch(crt,dp2.query(l+1,r)+(cnt[0][r]-cnt[1][r]));
    ll pre=dp.query(r,r+1);
    if(crt<pre) dp.update(r,crt);
    pre=dp2.query(r,r+1);
    if(crt-f[r]<pre) dp2.update(r,crt-f[r]);
  }
  cout<<dp.query(0,n+1)<<endl;
	return 0;
}

```