output_description: Find the minimum possible absolute difference of the maximum and the minimum
  among P,Q,R,S.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1 A_2 ... A_N
attempt: # 全体の和を求めて平均を出す。
  # 左から順に要素を見ていき、平均との差の絶対値が最小になった時点で確定
  # ただし、残りN個作る必要があるときに残数がN未満だったらその時点で確定する
  
  import sys
  
  readline = sys.stdin.readline
  
  N = int(readline())
  A = list(map(int, readline().split()))
  ave = sum(A) / 4
  # print(ave)
  # aveが目指す数字
  ind = 0
  data = [0] * 4
  for i in range(1, 5):
      # print("i",i,"ind",ind)
      # i個目のブロックについて探索する
  
      # これが最終ブロックの場合は、すべて採用する
      if i == 4:
          data[i - 1] = sum(A[ind:])
          break
      cur = 0
      diff = 0
      for j in range(ind, len(A) - (4 - i)):
          cur += A[j]
          # print("cur",cur)
          if cur == ave:
              # そのまま採用する
              ind = j + 1
              break
          if cur < ave:
              diff = abs(cur - ave)
              ind = j
              # print("diff",diff)
          else:
              # curがaveを追い抜いたとき
              # print("cur",cur,"がave",ave,"を追い抜いた")
              new_diff = abs(cur - ave)
              # print("new_diff",new_diff,"diff",diff)
              if j == ind:
                  # 最初は巻き戻せないのでそのまま採用
                  ind = j + 1
              elif new_diff <= diff:  # 新規の差分のほうが小さいので、そのまま採用
                  ind = j + 1
                  # print("採用")
              else:  # 巻き戻す
                  # print("巻き戻すcur",cur,"A[j]",A[j])
                  ind = j
                  cur -= A[j]
                  # print("cur",cur)
              break
      else:
          # breakしなかったときはそのまま採用
          ind = j + 1
      data[i - 1] = cur
      # print("data",data,"ind",ind)
  # print(data)
  print(max(data) - min(data))
  
problem_description: Statement
  
  Snuke has an integer sequence A of length N.
  
  He will make three cuts in A and divide it into four (non-empty) contiguous
  subsequences B, C, D and E. The positions of the cuts can be freely chosen.
  
  Let P,Q,R,S be the sums of the elements in B,C,D,E, respectively. Snuke is
  happier when the absolute difference of the maximum and the minimum among
  P,Q,R,S is smaller. Find the minimum possible absolute difference of the
  maximum and the minimum among P,Q,R,S.
samples: [{"input": "5\n    3 2 4 1 2", "output": "2\n    \n\nIf we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3. Here,\nthe maximum and the minimum among P,Q,R,S are 4 and 2, with the absolute\ndifference of 2. We cannot make the absolute difference of the maximum and the\nminimum less than 2, so the answer is 2.\n\n* * *"}, {"input": "10\n    10 71 84 33 6 47 23 25 52 64", "output": "36\n    \n\n* * *"}, {"input": "7\n    1 2 3 1000000000 4 5 6", "output": "999999994"}]