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>
#define ls x << 1
#define rs x << 1 | 1
using namespace std;
const int N = 2e5 + 10;
int a[N], qz[N][2];
int mn[N << 2], tag[N << 2];

void down(int x) {
  if(tag[x]) {
    mn[ls] += tag[x];
    tag[ls] += tag[x];
    mn[rs] += tag[x];
    tag[rs] += tag[x];
    tag[x] = 0;
  }
}

void upd(int x, int l, int r, int L, int w) {
  if(l == r) {
    mn[x] = min(mn[x], w);
    return ;
  }
  down(x);
  int mid = (l + r) >> 1;
  if(L <= mid) upd(ls, l, mid, L, w);
  else upd(rs, mid + 1, r, L, w);
  mn[x] = min(mn[ls], mn[rs]);
}

void add(int x, int l, int r, int L, int R, int w) {
  if(L <= l && r <= R) {
    mn[x] += w;
    tag[x] += w;
    return ;
  }
  down(x);
  int mid = (l + r) >> 1;
  if(L <= mid) add(ls, l, mid, L, R, w);
  if(R > mid) add(rs, mid + 1, r, L, R, w);
  mn[x] = min(mn[ls], mn[rs]);
}

int get(int x, int l, int r, int L, int R) {
  if(L <= l && r <= R) {
    return mn[x];
  }
  down(x);
  int mid = (l + r) >> 1;
  if(R <= mid) return get(ls, l, mid, L, R);
  else if(L > mid) return get(rs, mid + 1, r, L, R);
  else {
    return min(get(ls, l, mid, L, R), get(rs, mid + 1, r, L, R));
  }
}

struct data {
  int l, r;
} q[N];

bool cmp(data A, data B) {
  return A.l == B.l ? A.r < B.r : A.l < B.l;
}


int main() {
  memset(mn, 0x3f, sizeof mn);
  int n;
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i) {
    for(int j = 0; j < 2; ++j)
      qz[i][j] = qz[i - 1][j];
    scanf("%d", &a[i]);
    qz[i][a[i]]++;
  }
  upd(1, 0, n, 0, 0);
  int m;
  scanf("%d", &m);
  for(int i = 1; i <= m; ++i) {
    scanf("%d%d", &q[i].l, &q[i].r);
  }
  sort(q + 1, q + 1 + m, cmp);
  int lt = 1;
  for(int i = 1; i <= n; ++i) {
    for(; lt <= m && q[lt].l == i; ++lt)
      upd(1, 0, n, q[lt].r, get(1, 0, n, 0, q[lt].r));
    if(a[i])
      add(1, 0, n, 0, i - 1, 1);
    else 
      add(1, 0, n, 0, i - 1, -1);
  }
  printf("%d\n", get(1, 0, n, 0, n) + qz[n][0]);
  return 0;
}