Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import Counter

mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

C = Counter()
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            if C[i] < cnt:
                C[i] = cnt
        i += 1
    if a > 1:
        if C[a] < 1:
            C[a] = 1

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
    L %= mod

ans = 0
for a in A:
    ans += L * pow(a, mod - 2, mod)
    ans %= mod

print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

    L = reduce(lcm, A)
    print(sum(L // a for a in A) % mod)

main()
### BUGGY CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))
b = list(set(a))
l = b[0]
for i in b[1:]:
    l = l * i // fractions.gcd(l,i)
mod = 10**9+7
total = 0
for i in a:
    total += l//i
    if total > mod:
        total %= mod
print(total)

### FIXED CODE ###

#GCD, LCM
def gcd_base(a, b):
    while b!=0:
        a, b = b, a%b
    return a

def lcm(num_list):
    ans = 1
    for i in num_list:
        ans = ans * i // gcd_base(ans, i)
    return ans

n = int(input())
a = list(map(int, input().split()))
l = lcm(a)
mod = 10**9+7
total = 0
for i in a:
    total += l//i
print(total%mod)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
 
 
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
 
 
def lcm(a, b):
    return a * b // gcd(a, b)
 
 
tmp = A[0]
for i in range(1, N):
    tmp = lcm(tmp, A[i])
 
B = [0] * N
for i in range(N):
    B[i] = tmp // A[i]
 
print(sum(B) % mod)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
 
 
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
 
 
def lcm(a, b):
    return a * b // gcd(a, b)
 
 
tmp = A[0]
for i in range(1, N):
    tmp = lcm(tmp, A[i])
 
B = [0] * N
for i in range(N):
    B[i] = tmp // A[i]
 
print(sum(B) % mod)
### BUGGY CODE ###

n = int(input())
a = [input() for i in range(n)] 
ans =1
s = [a[0]]
 
for i in a[1:]:
    if not i in s:
        ans += 1
        s.append(i)
print(ans)

### FIXED CODE ###

import collections
N=int(input())
S=[]
for i in range(N):
    S.append(input())
s=collections.Counter(S)
s_key=s.keys()
print(len(s_key))
### BUGGY CODE ###

import bisect

n = int(input())
L = list(map(int,input().split()))
L.sort()
ans =0
for i in range(n):
  for j in range(i+1,n):
    L_ = L[j+1:]
    ans += bisect.bisect_left(L_,L[i]+L[j])-bisect.bisect_right(L_,abs(L[i]-L[j]))
print(ans)    
    

### FIXED CODE ###

import bisect

n = int(input())
L = list(map(int,input().split()))
L.sort()
ans =0
for i in range(n-1,1,-1):
  for j in range(i-1,0,-1):
    L_ = L[:j]
    ans += j-bisect.bisect_right(L_,L[i]-L[j])
    
print(ans)
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]

for j in range(1, n+1):
  for i in range(n):
    if A[i] ==j:
      print(i+1, end=" ")

### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]

L=[0]*n

for i in range(n):
  s = A[i]
  L[s-1] = i+1

print(*L)
### BUGGY CODE ###

n,m = map(int, input().split())
p = list(map(int,input().split()))
d = [list() for _ in range(n+1)]
cnt = 0
for _ in range(m):
  x,y = map(int, input().split())
  d[x].append(y)
  d[y].append(x)
gr = [0]*(n+1)
gr[0] = -1
gn = 0
for x in range(1,n+1):
  if gr[x] == 0:
    gn += 1
    gr[x] = gn
    l = [x]
    while l:
      cur = l.pop()
      for i in d[cur]:
        if i not in l and gr[i] == 0:
          gr[i] = gn
          l.append(i)
for i in range(n):
  if gr[i+1] == gr[p[i]]:
    cnt += 1
print(cnt)

### FIXED CODE ###

n,m = map(int, input().split())
p = list(map(int,input().split()))
d = [list() for _ in range(n+1)]
cnt = 0
for _ in range(m):
  x,y = map(int, input().split())
  d[x].append(y)
  d[y].append(x)
gr = [0]*(n+1)
gr[0] = -1
gn = 0
for x in range(1,n+1):
  if gr[x] == 0:
    gn += 1
    gr[x] = gn
    l = [x]
    while l:
      cur = l.pop()
      for i in d[cur]:
        if i not in l and gr[i] == 0:
          gr[i] = gn
          l.append(i)
for i in range(n):
  if gr[i+1] == gr[p[i]]:
    cnt += 1
print(cnt)
### BUGGY CODE ###

def bellman_ford(n, edges, s, distance=None):
    if distance != None:
        d = distance.copy()
    else :
        d = [float('inf')] * n
        d[s] = 0
    
    loop_cnt = 0
    while True:
        loop_cnt += 1
        update = False
        for i in range(len(edges)):
            e = edges[i]
            if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        
        if not update or loop_cnt > n: break
    return d

n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a-1, b-1, -c))

dist = bellman_ford(n, edges, 0)
test = bellman_ford(n, edges, 0, dist)

if dist[n-1] > test[n-1]:
    print("inf")
else :
    print(-dist[n-1])

### FIXED CODE ###

def bellman_ford(n, edges, s, distance=None):
    if distance != None:
        d = distance[:]
    else :
        d = [float('inf')] * n
        d[s] = 0
    
    loop_cnt = 0
    while True:
        loop_cnt += 1
        update = False
        for i in range(len(edges)):
            e = edges[i]
            if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True

        if not update or loop_cnt > n: break
    return d

n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a-1, b-1, -c))

dist = bellman_ford(n, edges, 0)
test = bellman_ford(n, edges, 0, dist)

if dist[n-1] != test[n-1]:
    print("inf")
else :
    print(-dist[n-1])
### BUGGY CODE ###

import numpy as np
import sys
import math

S = input()

tmp = []

for i in range(1,50008):
    x = 2019 * i
    if str(x).find("0") == -1:
        tmp.append(x)

ans = 0
ll = len(S)
for wide in range(5,9):
    for i in range(ll - wide + 1):
        if i + wide > ll:
            break
        ss = int(S[i:i+wide])
        if ss in tmp:
            ans += 1
        else:
            continue
        index = 0
        while True :
            flag = 0
            for ww in range(5,9):
                if i + wide + 1 + index + index + ww >=  ll :
                    flag  = 1
                    break
                if int(S[i+wide + 1 + index : i + wide + 1 + index + ww]) in tmp:
                    ans += 1
                index += 8
            if flag == 1:
                break

print(ans)

### FIXED CODE ###

import numpy as np
import sys
import math

S = input()

mm = [0] * (2019)
mm[0] = 1
a = [0] * (len(S) + 1 ) 
T = 0
ten = 1
ll = len(S)
for i in range(ll):
    if i > 0:
        ten = ( ten * 10 ) % 2019
    a[i+1] =  ( a[i] + (int(S[ll-1-i])*ten ) ) % 2019
    mm[ a[i+1] ] += 1
    #print(s)

ans = 0

for m in mm:
    ans += int( (m * (m-1) ) / 2 )

print(ans)
### BUGGY CODE ###

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
    # ノードxのrootノードを見つける
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
    # 木の併合、入力は併合したい各ノード⇒(a,b)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
    # ノードxが属する木のサイズを返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
    # 入力ノード(x,y)が同じグループに属するかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
    #ノードxが属するメンバーをリスト形式で返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
    #親全てをリスト形式で返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
    #グループ数の合計を返す
        return len(self.roots())

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n,m=map(int,input().split())
u=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    u.unite(a,b)
ans=0
for i in range(n):
    ans=u.roots()
print(len(ans)-1)


### FIXED CODE ###

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
    # ノードxのrootノードを見つける
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
    # 木の併合、入力は併合したい各ノード⇒(a,b)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
    # ノードxが属する木のサイズを返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
    # 入力ノード(x,y)が同じグループに属するかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
    #ノードxが属するメンバーをリスト形式で返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
    #親全てをリスト形式で返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
    #グループ数の合計を返す
        return len(self.roots())

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n,m=map(int,input().split())
u=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    u.unite(a,b)
ans=u.roots()
print(len(ans)-1)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N+1):
    print(A.count(i))


### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
c = collections.Counter(A)
for i in range(1,N+1):
    print(c[i])
### BUGGY CODE ###

nums = int(input())
ary  = list(map(int,input().split()))
count =0
max_count = 0
ary.sort()
ary_count = [0 for i in range(100005)]
ary_count.append(0)

for i in range(100005):
    ary_count[i] = ary.count(i)

for i in range(1,100005):
    count += ary_count[i]
    count += ary_count[i+1]
    count += ary_count[i-1]
    if count > max_count:
        max_count = count
    count = 0
print(max_count)

### FIXED CODE ###

nums = int(input())
ary  = list(map(int,input().split()))
count =0
max_count = 0
ary.sort()
ary_count = [0 for i in range(100005)]
ary_count.append(0)

for i in ary:
    ary_count[i] += 1

for i in range(1,100005):
    count += ary_count[i]
    count += ary_count[i+1]
    count += ary_count[i-1]
    if count > max_count:
        max_count = count
    count = 0
print(max_count)
### BUGGY CODE ###

from operator import itemgetter

n, m  = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for i in range(m)]

bc = sorted(bc, key=itemgetter(1))

for i in range(m):
  a.sort()
  for j in range(bc[i][0]):
    if a[j] < bc[i][1]:
      a[j] = bc[i][1]
    else:
      continue
      
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cb=[]
for i in range(m):
    b, c = map(int, input().split())
    cb.append([c,b])
cb.sort(reverse=True)
k=0
for i in range(m):
    j=0
    while j<cb[i][1] and k+j<n and a[k+j]<cb[i][0]:
        a[k+j] = cb[i][0]
        j+=1
    k+=j
    if k==n:
        break
print(sum(a))
### BUGGY CODE ###

import sys

from itertools import combinations

n, m = map(int, input().split())
survivors = {v: {v + 1} for v in range(n)}
for x, y in reversed(list(map(int, line.split()) for line in sys.stdin.readlines())):
    for v, srv in survivors.copy().items():
        if x in srv:
            if y in srv:
                del survivors[v]
            else:
                srv.add(y)
        elif y in srv:
            srv.add(x)
print(sum(su.isdisjoint(sv) for su, sv in combinations(survivors.values(), 2)))


### FIXED CODE ###

def get_survivors(n, pairs):
    survivors = {v: {v} for v in range(n)}
    for x, y in reversed(pairs):
        for v, srv in survivors.copy().items():
            if x in srv:
                if y in srv:
                    del survivors[v]
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
    return survivors


def solve(n, pairs):
    survivors = get_survivors(n, pairs)
    ans = 0
    for u, su in survivors.items():
        for v, sv in survivors.items():
            if u >= v:
                continue
            if su.isdisjoint(sv):
                ans += 1
    return ans


n, m = map(int, input().split())
pairs = []
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    pairs.append((x, y))
print(solve(n, pairs))
### BUGGY CODE ###

import copy

n = int(input())

a = [0] * n

for i in range(n):
    a[i] = int(input())

# a_s = set(a)

for i in range(n):
    tmp = copy.deepcopy(a)
    # tmp.discard(a[i])
    del tmp[i]
    print(max(tmp))


### FIXED CODE ###

import copy

n = int(input())

a = [0] * n

for i in range(n):
    a[i] = int(input())

a_sort = sorted(a, reverse=True)

for i in range(n):
    if a[i] == a_sort[0]:
        print(a_sort[1])
    else:
        print(a_sort[0])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

# ans = []
# for i in range(N):

tmp = sorted(A)
dic = {}
for t in tmp:
    dic[t] = tmp.count(t)

# print(dic)

for i in range(N):
    # tmp = dic.get(A[i])
    ans = 0
    for key in list(dic.keys()):
        val = dic.get(key)
        if key == A[i]:
            val -= 1
        # print(key)
        # print(val)
        # print("\t"+str(val * (val - 1) // 2))
        ans += val * (val - 1) // 2
    print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

dic = {}
ans = 0
# for t in A:
#     if t in dic.keys():
#         continue
#     tmp = A.count(t)
#     dic[t] = tmp
#     ans += tmp*(tmp-1)//2

for a in A:
    tmp = dic.get(a)
    if tmp == None:
        dic[a] = 1
    else:
        dic[a] = tmp + 1

for key in list(dic.keys()):
    tmp = dic.get(key)
    ans += tmp * (tmp - 1) // 2
    

for a in A:
    val = dic.get(a)
    print(ans-val+1)
### BUGGY CODE ###

n,m = map(int, input().split())
a = list(map(int,input().split()))
MIN = min(a)
p = []
for _ in range(m):
    b,c = map(int, input().split())  
    if c > MIN:
        p.extend([c]*b)

ans = (a+p)
ans.sort(reverse=True)
print(sum(ans[:n]))

### FIXED CODE ###

n,m = map(int, input().split())
a = sorted(list(map(int,input().split())))
bc = [list(map(int, input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1], reverse=True )
count = 0
for b,c in bc:
    for _ in range(b):
        if count == n or a[count] >= c:
            break

        a[count] = c
        count += 1

print(sum(a))
### BUGGY CODE ###

a,b,k = map(int,input().split())
ans = list(map(int,range(a,b+1)))
# print(ans)
for i in sorted(list(map(int,set(ans[:k]+ans[-k:])))):
    print(i)
# print(set(ans[:k]+ans[-k:]))

### FIXED CODE ###

a,b,k = map(int,input().split())
ans = []
ans.append(a)
ans.append(b)
for i in range(min(k,b-a)):
    ans.append(a+i)
    ans.append(b-i)
ans = list(set(ans))
ans.sort()
for i in ans:
    print(i)
# print(ans)
### BUGGY CODE ###

import sys
from collections import deque

import numpy as np

input = sys.stdin.readline


def bfs(H, W, A, dist):
    queue = deque([])
    for h, w in zip(*np.where(A == "#")):
        dist[h, w] = 0
        queue.append((h, w))
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_h, next_w = h + y, w + x
            if not (0 <= next_h < H and 0 <= next_w < W):
                continue
            if dist[next_h][next_w] == -1:
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append((next_h, next_w))

    return dist.max()


def main():
    H, W = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=str)
    for i in range(H):
        A[i] = list(input().rstrip())

    dist = np.full(shape=(H, W), fill_value=-1, dtype=np.int32)
    ans = bfs(H, W, A, dist)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, A, dist):
    queue = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                dist[h][w] = 0
                queue.append((h, w))
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_h, next_w = h + y, w + x
            if dist[next_h][next_w] == -1:
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append((next_h, next_w))


def main():
    H, W = map(int, input().split())
    A = [None] * (H + 2)
    A[0] = A[-1] = "." * (W + 2)
    for i in range(1, H + 1):
        A[i] = "".join([".", input().rstrip(), "."])

    dist = [[0] + [-1] * W + [0] for _ in range(H + 2)]
    dist[0] = dist[-1] = [0] * (W + 2)
    bfs(H + 2, W + 2, A, dist)

    ans = max(map(max, dist))
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: y[1] / y[0] - x[1] / x[0]))
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  updates = []
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw not in t or nv > t[nw]:
      for u in updates:
        if nw <= u[0] and nv <= u[1]:
          continue
      updates.append([nw, nv])
  for u in updates:
    t[u[0]] = u[1]
print(max(t.values()))


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

import numpy as np
n,m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
for i in range(m):
    k = np.argmax(a)
    a[k] = int(a[k]/2)
ans = sum(a)
print(ans)


### FIXED CODE ###

#import numpy as np
import sys
import heapq #優先度付きキュー
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
a = [int(i)*(-1) for i in input().split()] #各要素*(-1)
heapq.heapify(a)
for i in range(m):
    """
    k = np.argmax(a)
    if a[k] == 0:
        break
    a[k] = int(a[k]/2)
    """
    tmp = heapq.heappop(a) #最小値を抜き取る(最大値*(-1)を抜き取る）
    heapq.heappush(a, (-1)*(-tmp//2)) #要素を追加
ans = -sum(a)
print(ans)
### BUGGY CODE ###

n,m=[int(i) for i in input().split()]
P=[[int(i) for i in input().split()] for j in range(m)]

def prefecturesort(i):
    return i[0]

def yearsort(i):
    return i[1]

W=[]
Z=[]

for i in range(m):
    P[i].append(i)
    W.append(P[i][0])

P.sort(key=prefecturesort)
P_c=[]
sum=0
for i in range(n):
    c=W.count(i+1)
    if c==0:
        P_c.append([])
    else:
        P_c.append(P[sum:c+sum])
    sum+=c
for i in range(n):
    P_c[i].sort(key=yearsort)
for x in P_c:
    for j in range(len(x)):
        X="{0:06d}".format(x[j][0])
        Y="{0:06d}".format(j+1)
        X=str(X)
        Y=str(Y)
        Z.append([X+Y,x[j][2]])
Z.sort(key=yearsort)
for i in range(m):
    print(Z[i][0])

### FIXED CODE ###

n,m=[int(i) for i in input().split()]
P=[[int(i) for i in input().split()] for j in range(m)]

def prefecturesort(i):
    return i[0]

def yearsort(i):
    return i[1]

W=[0 for i in range(n)]
Z=[]

for i in range(m):
    P[i].append(i)
    W[P[i][0]-1]+=1

P.sort(key=prefecturesort)
P_c=[]
sum=0
for i in range(n):
    c=W[i]
    if c==0:
        P_c.append([])
    else:
        P_c.append(P[sum:c+sum])
    sum+=c
    P_c[i].sort(key=yearsort)
for x in P_c:
    for j in range(len(x)):
        X=str("{0:06d}".format(x[j][0]))
        Y=str("{0:06d}".format(j+1))
        Z.append([X+Y,x[j][2]])
Z.sort(key=yearsort)
for i in range(m):
    print(Z[i][0])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
R = [0] * (N + 1)
for i in range(N):
  R[i + 1] += R[i] + A[i]
#print(R)  

ans = 10 ** 15
for i in range(3, N):#R[:i]とR[i:]に切る
  l, r = 2, i + 1
  #R[:l], R[l:i], R[i:r], R[r:]
  #R[l - 1] と R[i - 1] - R[l - 1] の差を考える
  
  while abs(R[i - 1] - 2 * R[l]) <= abs(R[i - 1] - 2 * R[l - 1]):
    l += 1
    
  #R[r - 1] - R [i - 1] と R[N] - R[r - 1] の差を考える  
  while abs(R[N] - 2 * R[r] + R[i - 1]) <= abs(R[N] - 2 * R[r - 1] + R[i - 1]):
    r += 1  
  
  now_max = max(max(R[l - 1], R[i - 1] - R[l - 1]), max(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  now_min = min(min(R[l - 1], R[i - 1] - R[l - 1]), min(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  ans = min(ans, now_max - now_min)
  #print(a, b, c, d, ans, ans2)
print(ans)
    
  
  

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
R = [0] * (N + 1)
for i in range(N):
  R[i + 1] += R[i] + A[i]
#print(R)  

ans = 10 ** 15
l, r = 2, 4
for i in range(3, N):#R[:i]とR[i:]に切る
  #R[:l], R[l:i], R[i:r], R[r:]
  #R[l - 1] と R[i - 1] - R[l - 1] の差を考える
  
  while abs(R[i - 1] - 2 * R[l]) <= abs(R[i - 1] - 2 * R[l - 1]):
    l += 1
    
  #R[r - 1] - R [i - 1] と R[N] - R[r - 1] の差を考える  
  while abs(R[N] - 2 * R[r] + R[i - 1]) <= abs(R[N] - 2 * R[r - 1] + R[i - 1]):
    r += 1  
  
  now_max = max(max(R[l - 1], R[i - 1] - R[l - 1]), max(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  now_min = min(min(R[l - 1], R[i - 1] - R[l - 1]), min(R[r - 1] - R[i - 1], R[N] - R[r - 1]))
  ans = min(ans, now_max - now_min)
  #print(R[l - 1], R[i - 1] - R[l - 1],R[r - 1] - R[i - 1], R[N] - R[r - 1], ans)
print(ans)