#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
using ll = long long;
using P = pair<ll, ll>;

//
// BEGIN Range minimum query
//

struct {
    int N;
    vector<long long> dat;

    void init(int n) {
      N = 1;
      while(N < n) N *= 2;
      dat.resize(2*N-1, LLONG_MAX);
    }

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

    // add k-th element by a
    void add(int k, long long a) {
      k += N-1;
      dat[k] += a;
      while(k > 0) {
        k = (k-1)/2;
        dat[k] = min(dat[k*2+1], dat[k*2+2]);
      }
    }

    // return k-th element
    long long get(int k) {
      return dat[k+N-1];
    }

    // return min[a, b)
    long long query(int a, int b) {
      return query(a, b, 0, 0, N);
    }
    long long query(int a, int b, int k, int l, int r) {
      if (r <= a || b <= l) return LLONG_MAX;
      if (a <= l && r <= b) return dat[k];
      int m = (l+r)/2;
      return min(query(a, b, k*2+1, l, m), query(a, b, k*2+2, m, r));
    }
} S;

//
// END range_minimum_query
//

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  S.init(n+1);
  vector<int> b(n);
  int zero = 0;
  rep(i, n) {
    cin >> b[i];
    if (b[i]==0) zero++;
  }
  int q; cin >> q;
  vector<P> ra(q);
  rep(i, q) {
    ll l, r; cin >> l >> r;
    ra[i].first = l;
    ra[i].second = r;
  }
  sort(ra.begin(), ra.end());
  S.update(0, 0);
  int j = 0;
  for(int i=1; i<=n; i++) {
    while(j < q && ra[j].first==i) {
      int l = ra[j].first;
      int r = ra[j].second;
      auto mi = S.query(l-1, r);
      if (mi < S.get(r)) {
        S.update(r, mi);
      }
      j++;
    }
    auto p = (b[i-1]==0) ? -1 : 1;
    auto mi = S.get(i-1)+p;
    if (mi < S.get(i)) {
      S.update(i, mi);
    }
  }
  cout << zero+S.get(n) << endl;
}
### Prompt

Your challenge is to write 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;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
using ll = long long;
using P = pair<ll, ll>;

//
// BEGIN Range minimum query
//

struct {
    int N;
    vector<long long> dat;

    void init(int n) {
      N = 1;
      while(N < n) N *= 2;
      dat.resize(2*N-1, LLONG_MAX);
    }

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

    // add k-th element by a
    void add(int k, long long a) {
      k += N-1;
      dat[k] += a;
      while(k > 0) {
        k = (k-1)/2;
        dat[k] = min(dat[k*2+1], dat[k*2+2]);
      }
    }

    // return k-th element
    long long get(int k) {
      return dat[k+N-1];
    }

    // return min[a, b)
    long long query(int a, int b) {
      return query(a, b, 0, 0, N);
    }
    long long query(int a, int b, int k, int l, int r) {
      if (r <= a || b <= l) return LLONG_MAX;
      if (a <= l && r <= b) return dat[k];
      int m = (l+r)/2;
      return min(query(a, b, k*2+1, l, m), query(a, b, k*2+2, m, r));
    }
} S;

//
// END range_minimum_query
//

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  S.init(n+1);
  vector<int> b(n);
  int zero = 0;
  rep(i, n) {
    cin >> b[i];
    if (b[i]==0) zero++;
  }
  int q; cin >> q;
  vector<P> ra(q);
  rep(i, q) {
    ll l, r; cin >> l >> r;
    ra[i].first = l;
    ra[i].second = r;
  }
  sort(ra.begin(), ra.end());
  S.update(0, 0);
  int j = 0;
  for(int i=1; i<=n; i++) {
    while(j < q && ra[j].first==i) {
      int l = ra[j].first;
      int r = ra[j].second;
      auto mi = S.query(l-1, r);
      if (mi < S.get(r)) {
        S.update(r, mi);
      }
      j++;
    }
    auto p = (b[i-1]==0) ? -1 : 1;
    auto mi = S.get(i-1)+p;
    if (mi < S.get(i)) {
      S.update(i, mi);
    }
  }
  cout << zero+S.get(n) << endl;
}
```