output_description: Print the minimum possible hamming distance.
  
  * * *
input_description: 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
attempt: import sys
  
  readline = sys.stdin.readline
  readlines = sys.stdin.readlines
  import itertools
  
  N = int(readline())
  B = [int(x) for x in readline().split()]
  Q = int(readline())
  LR = sorted(
      [tuple(int(x) for x in line.split()) for line in readlines()], key=lambda x: x[1]
  )
  
  """
  Rが手前のものから処理。その時点で、Bと一致できているセルの個数を最大化したい
  代わりに、「「00000」から見た改善量」をdpとして持つ。
  区間[L,R] を最後に使うとき、手前はdp[0,...,L-1]の最大値でとりたい。
  よって、dpの区間maxをBITで管理すればよい
  """
  
  # 1とおいたときの改善量
  improve_cum = [0] + list(itertools.accumulate(2 * x - 1 for x in B))
  
  
  def BIT_update(tree, i, x):
      while i <= N and tree[i] < x:
          tree[i] = x
          i += i & (-i)
  
  
  def BIT_max(tree, i):
      ret = 0
      while i:
          if ret < tree[i]:
              ret = tree[i]
          i -= i & (-i)
      return ret
  
  
  dp = [0] * (N + 1)
  
  for L, R in LR:
      x = improve_cum[R] - improve_cum[L - 1]  # 区間[L,R] での改善量
      x += BIT_max(dp, L - 1)  # [0,L-1]での改善量の最大値
      BIT_update(dp, R, x)
  
  base_score = sum(B)
  answer = base_score - max(dp)
  print(answer)
  
problem_description: Statement
  
  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.
samples: [{"input": "3\n    1 0 1\n    1\n    1 3", "output": "1\n    \n\nIf you choose to perform the operation, a will become \\\\{1, 1, 1\\\\}, for a\nhamming distance of 1.\n\n* * *"}, {"input": "3\n    1 0 1\n    2\n    1 1\n    3 3", "output": "0\n    \n\nIf both operations are performed, a will become \\\\{1, 0, 1\\\\}, for a hamming\ndistance of 0.\n\n* * *"}, {"input": "3\n    1 0 1\n    2\n    1 1\n    2 3", "output": "1\n    \n\n* * *"}, {"input": "5\n    0 1 0 1 0\n    1\n    1 5", "output": "2\n    \n\nIt may be optimal to perform no operation.\n\n* * *"}, {"input": "9\n    0 1 0 1 1 1 0 1 0\n    3\n    1 4\n    5 8\n    6 7", "output": "3\n    \n\n* * *"}, {"input": "15\n    1 1 0 0 0 0 0 0 1 0 1 1 1 0 0\n    9\n    4 10\n    13 14\n    1 7\n    4 14\n    9 11\n    2 6\n    7 8\n    3 12\n    7 13", "output": "5\n    \n\n* * *"}, {"input": "10\n    0 0 0 1 0 0 1 1 1 0\n    7\n    1 4\n    2 5\n    1 3\n    6 7\n    9 9\n    1 5\n    7 9", "output": "1"}]