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: #!/usr/bin/env python3
  # coding: utf-8
  
  from sys import stdin
  
  
  def cost_gain(lr):
      global bs
      l, r = lr
      sb = bs[l - 1 : r]
      cost = sum(1 for b in sb if b == "0")
      gain = sum(1 for b in sb if b == "1")
      return cost, gain
  
  
  def key(lr):
      cost, gain = cost_gain(lr)
      return (cost, -gain, lr)
  
  
  def solve(lr):
      global bs
      dist = sum(1 for b in bs if b == "1")
      while True:
          lr.sort(key=key)
          cost, gain = cost_gain(lr[0])
          if cost >= gain:
              break
          l, r = lr[0]
          for i in range(l - 1, r):
              bs[i] = "*"
          dist += cost - gain
      return dist
  
  
  N = int(stdin.readline())
  bs = [w for w in stdin.readline().split()]
  Q = int(stdin.readline())
  lr = []
  for i in range(Q):
      l, r = [int(w) for w in stdin.readline().split()]
      lr.append((l, r))
  if len(bs) != N:
      raise
  if len(lr) != Q:
      raise
  
  print(solve(lr))
  
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"}]