#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

struct SegmentTree {
  vint data;
  int sz;
  SegmentTree(int n) {
    sz = 1; while(sz < n) sz <<= 1;
    resz(data, 2*sz-1, -inf);
  }
  void set(int k, int x) {
    k += sz-1;
    data[k] = x;
    while(k > 0) {
      k = (k-1)/2;
      data[k] = max(data[2*k+1], data[2*k+2]);
    }
  }
  int query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return -inf;
    if(a <= l && r <= b) return data[k];
    int vl = query(a, b, 2*k+1, l, (l+r)/2);
    int vr = query(a, b, 2*k+2, (l+r)/2, r);
    return max(vl, vr);
  }
  int query(int a, int b) {
    return query(a, b, 0, 0, sz);
  }
};

int N, Q;
vint b, l, r;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> N;
  resz(b, N);
  rep(i, N) cin >> b[i];
  cin >> Q;
  resz(l, Q);
  resz(r, Q);
  rep(i, Q) cin >> l[i] >> r[i], --l[i];

  vint one(N+1);
  rep(i, N) one[i+1] = one[i] + b[i];

  auto get = [&one](int l, int r) {
    return (one[r]-one[l]);
  };

  vector<Pi> q;
  rep(i, Q) q.emplace_back(l[i], r[i]);
  sort(all(q));

  vint dp(N+1, -inf);
  SegmentTree seg(N+1);
  rep(i, N+1) seg.set(i, -one[i]);
  dp[0] = 0;
  int p = 0;
  rep(i, Q) {
    int l, r;
    tie(l, r) = q[i];
    while(p < l) {
      chmax(dp[p+1], dp[p]+1-b[p]);
      ++p;
      seg.set(p, dp[p]-one[p]);
    }
    chmax(dp[r], seg.query(l, r)+one[r]);
    seg.set(r, dp[r]-one[r]);
  }
  while(p < N) chmax(dp[p+1], dp[p]+1-b[p]), ++p;
  cout << N-dp[N] << endl;

  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

struct SegmentTree {
  vint data;
  int sz;
  SegmentTree(int n) {
    sz = 1; while(sz < n) sz <<= 1;
    resz(data, 2*sz-1, -inf);
  }
  void set(int k, int x) {
    k += sz-1;
    data[k] = x;
    while(k > 0) {
      k = (k-1)/2;
      data[k] = max(data[2*k+1], data[2*k+2]);
    }
  }
  int query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return -inf;
    if(a <= l && r <= b) return data[k];
    int vl = query(a, b, 2*k+1, l, (l+r)/2);
    int vr = query(a, b, 2*k+2, (l+r)/2, r);
    return max(vl, vr);
  }
  int query(int a, int b) {
    return query(a, b, 0, 0, sz);
  }
};

int N, Q;
vint b, l, r;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> N;
  resz(b, N);
  rep(i, N) cin >> b[i];
  cin >> Q;
  resz(l, Q);
  resz(r, Q);
  rep(i, Q) cin >> l[i] >> r[i], --l[i];

  vint one(N+1);
  rep(i, N) one[i+1] = one[i] + b[i];

  auto get = [&one](int l, int r) {
    return (one[r]-one[l]);
  };

  vector<Pi> q;
  rep(i, Q) q.emplace_back(l[i], r[i]);
  sort(all(q));

  vint dp(N+1, -inf);
  SegmentTree seg(N+1);
  rep(i, N+1) seg.set(i, -one[i]);
  dp[0] = 0;
  int p = 0;
  rep(i, Q) {
    int l, r;
    tie(l, r) = q[i];
    while(p < l) {
      chmax(dp[p+1], dp[p]+1-b[p]);
      ++p;
      seg.set(p, dp[p]-one[p]);
    }
    chmax(dp[r], seg.query(l, r)+one[r]);
    seg.set(r, dp[r]-one[r]);
  }
  while(p < N) chmax(dp[p+1], dp[p]+1-b[p]), ++p;
  cout << N-dp[N] << endl;

  return 0;
}

```