output_description: Print the answer.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      a_{0} a_{1} ... a_{N-1}
attempt: import sys
  
  N = int(sys.stdin.readline())
  S = list(sys.stdin.readline())
  Q = int(sys.stdin.readline())
  k = list(map(int, sys.stdin.readline().split(" ")))
  
  # chache = []
  
  oms = [(i, S[i]) for i in range(N) if S[i] == "D" or S[i] == "M" or S[i] == "C"]
  oml = len(oms)
  
  
  def process(ki, index, selected="n"):
      global cache
  
      if index == oml:
          return []
  
      if cache[index][selected] is not None:
          # print('use cache')
          return cache[index][selected]
  
      rets = []
      # char = oms[index][1]
      if selected == "b":
          for ind in range(index, oml):
              char = oms[ind][1]
              if char == "C":
                  rets.append(oms[ind][0])
      elif selected == "a":
          for ind in range(index, oml):
              char = oms[ind][1]
              if char == "M":
                  rets += process(ki, ind + 1, "b")
      else:
          for ind in range(index, oml):
              char = oms[ind][1]
              if char == "D":
                  cind = process(ki, ind + 1, "a")
                  ret = []
                  for v in cind:
                      if v != False and ((v - oms[ind][0]) < ki):
                          ret.append(True)
                  rets += ret
  
      cache[index][selected] = rets
  
      return rets
  
  
  for ki in k:
      cache = [{"a": None, "b": None, "c": None, "n": None} for i in range(oml)]
      ret = process(ki, 0)
      print(len(ret))
  
problem_description: Statement
  
  Niwango-kun is an employee of Dwango Co., Ltd.  
  One day, he is asked to generate a thumbnail from a video a user submitted.  
  To generate a thumbnail, he needs to select a frame of the video according to
  the following procedure:
  
    * Get an integer N and N integers a_0, a_1, ..., a_{N-1} as inputs. N denotes the number of the frames of the video, and each a_i denotes the representation of the i-th frame of the video.
    * Select t-th frame whose representation a_t is nearest to the average of all frame representations.
    * If there are multiple such frames, select the frame with the smallest index.
  
  Find the index t of the frame he should select to generate a thumbnail.
samples: [{"input": "3\n    1 2 3", "output": "1\n    \n\nSince the average of frame representations is 2, Niwango-kun needs to select\nthe index 1, whose representation is 2, that is, the nearest value to the\naverage.\n\n* * *"}, {"input": "4\n    2 5 2 5", "output": "0\n    \n\nThe average of frame representations is 3.5.  \nIn this case, every frame has the same distance from its representation to the\naverage.  \nTherefore, Niwango-kun should select index 0, the smallest index among them."}]