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.

-----Sample Input-----
3
1 0 1
1
1 3

-----Sample Output-----
1

If you choose to perform the operation, a will become \{1, 1, 1\}, for a hamming distance of 1.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\n\ninput=sys.stdin.readline\n\nn=int(input())\nb=list(map(int,input().split()))\nope=[[] for i in range(n)]\nQ=int(input())\nfor i in range(Q):\n    l,r=list(map(int,input().split()))\n    ope[r-1].append(l-1)\n\nres=b.count(0)\n\nData=[(-1)**((b[i]==1)+1) for i in range(n)]\nfor i in range(1,n):\n    Data[i]+=Data[i-1]\nData=[0]+Data\n\nfor i in range(n):\n    ope[i].sort(reverse=True)\n\n# N: 処理する区間の長さ\nN=n+1\nN0 = 2**(N-1).bit_length()\ndata = [None]*(2*N0)\nINF = (-2**31, -2**31)\n# 区間[l, r+1)の値をvに書き換える\n# vは(t, value)という値にする (新しい値ほどtは大きくなる)\ndef update(l, r, v):\n    L = l + N0; R = r + N0\n    while L < R:\n        if R & 1:\n            R -= 1\n            if data[R-1]:\n                data[R-1] = max(v,data[R-1])\n            else:\n                data[R-1]=v\n\n        if L & 1:\n            if data[L-1]:\n                data[L-1] = max(v,data[L-1])\n            else:\n                data[L-1]=v\n            L += 1\n        L >>= 1; R >>= 1\n# a_iの現在の値を取得\ndef _query(k):\n    k += N0-1\n    s = INF\n    while k >= 0:\n        if data[k]:\n            s = max(s, data[k])\n        k = (k - 1) // 2\n    return s\n# これを呼び出す\ndef query(k):\n    return _query(k)[1]\n\nfor i in range(n+1):\n    update(i,i+1,(-Data[i],-Data[i]))\nif ope[0]:\n    update(1,2,(0,0))\n\nfor i in range(1,n):\n    val=query(i)\n    update(i+1,i+2,(val+Data[i]-Data[i+1],val+Data[i]-Data[i+1]))\n    for l in ope[i]:\n        val=query(l)\n        update(l+1,i+2,(val,val))\n\n\n\nprint((n-(res+query(n)+Data[n])))\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14101