Harryxun/stf_run huggingface dataset:
from copy import deepcopy
from collections import deque
from functools import partial, lru_cache
from heapq import heappush, heappop

inputs = open(0).readlines()
n, k = map(int, inputs[0].split())
V = deque(map(int, inputs[1].split()))
W = []


def dfs(root, option, function):
    nodes, stack = [], [root]
    ans = 0
    while stack:
        current_node = stack.pop()
        if current_node in nodes:
            continue
        ans = function(current_node, ans)
        for n in option(current_node):
            if n not in nodes:
                stack.append(n)
    return ans

def option(node, k):
    i, j = node
    if i+j < k:
        return ((i+1, j), (i, j+1))
    return tuple()

def function(node, ans, W, V, k, memo):
    if node in memo:
        return max(ans, memo[node])

    i, j = node
    W_, V_ = get_W_V(i)
    for _ in range(j):
        if V_:
            heappush(W_, V_.popleft())
    score = sum(W_)
    for _ in range(min(k-i-j, i+j)):
        if W_ and W_[0] < 0:
            score -= heappop(W_)
    memo[node] = score
    return max(ans, memo[node])

ans = dfs((0, 0), partial(option, k=k), partial(function, W=W, V=V, k=k, memo={}))
print(ans)

### FIXED CODE ###

from collections import deque

inputs = open(0).readlines()
n, k = map(int, inputs[0].split())
V = deque(map(int, inputs[1].split()))
def calc(ii, jj, kk):
    W = []
    for i in range(ii):
        W.append(V[i])
    for j in range(jj):
        W.append(V[-j-1])
    W.sort(reverse=True)
    for _ in range(kk):
        if W[-1] < 0:
            W.pop()
    return sum(W)

ans = 0
for i in range(min(n, k)+1):
    for j in range(min(n, k)+1-i):
        for k_ in range(min(i+j, k+1-i-j)):
            ans = max(ans, calc(i, j, k_))
print(ans)
from math import gcd
N = int(input())
As = list(map(int, input().split()))

lis = [0]*N
ans = 0
for k in range(N):
    g = 10**20
    for i in range(N-1):
        if i==k: continue
        for j in range(i+1, N):
            if j==k: continue
            g = min(gcd(As[i], As[j]), g)
    ans = max(ans, g)
if N==2:
    print(max(As))
else:
    print(ans)
        

### FIXED CODE ###

from fractions import gcd

N = int(input())
As = list(map(int, input().split()))
re_As = As[::-1]
gcds = [0]*(N)
rgcds = [0]*(N)
gcds[0] = 0
rgcds[0] = 0

for i in range(N-1):
    gcds[i+1] = gcd(As[i], gcds[i])
    rgcds[i+1] = gcd(re_As[i], rgcds[i])

rgcds = rgcds[::-1]

ans = [0]*(N+1)

for i, (s, r) in enumerate(zip(gcds, rgcds)):
    ans[i] = gcd(s, r)
    
print(max(ans))
N = int(input())
S = input()
ans = 0
for i in range(N):
    if S[i] == "A" and i <= N - 2:
        if S[i + 1] == "B":
            if S[i + 2] == "C":
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(N - 2):
    if S[i] == "A" :
        if S[i + 1] == "B":
            if S[i + 2] == "C":
                ans += 1
print(ans)
import sys
input = sys.stdin.readline


x = int(input())

prime = [True] * (1000000)
prime[2] = True

def e_prime(x):
	i = 2
	flag = False
	while True:
		if prime[i]:
			if(flag==True):
				return i
			else:
				for j in range(i**2,len(prime),i):
					prime[j]=False
		i+=1
		if(i==x):flag=True

print(e_prime(x))

### FIXED CODE ###

import sys
input=sys.stdin.readline

a,b,k = map(int,input().split())

a_a =  0 if(a <= k) else a - k
if(a_a > 0):
	b_a = b
else:
	if(k-a>=b):
		b_a = 0
	else:
		b_a = b+a-k
print(a_a, b_a)
#from fractions import gcd
import math
A,B,C,D = map(int,input().split())
num_gcd = C*D//math.gcd(C,D)
ans_B = 0 - B//C - B//D + B//num_gcd
ans_A = 0 - (A-1)//C - (A-1)//D + (A-1)//num_gcd
ans = B - A + 1 + ans_B - ans_A
print(ans)

### FIXED CODE ###

import fractions
A,B,C,D = map(int,input().split())
num_gcd = C*D//fractions.gcd(C,D)
ans_B = 0 - B//C - B//D + B//num_gcd
ans_A = 0 - (A-1)//C - (A-1)//D + (A-1)//num_gcd
ans = B - A + 1 + ans_B - ans_A
print(ans)
n = int(input())
xy = []
for _ in range(n):
  xy.append(list(map(int,input().split())))
can = []
for i in range(n):
  now = [0,0]
  xp = [0,0]
  xm = [0,0]
  X = - xy[i][1] + 0.00000000000001
  Y = xy[i][0]
  for j in range(n):
    x,y = xy[j]
    if x * X + y * Y > 0:
      now[0] += x
      now[1] += y
    elif x * X + y * Y == 0:
      if x == 0:
        if y > 0:
          xp[0] += x
          xp[1] += y
        else:
          xm[0] += x
          xm[1] += y
      elif x > 0:
        xp[0] += x
        xp[1] += y
      else:
        xm[0] += x
        xm[1] += y
  xp[0] += now[0]
  xp[1] += now[1]
  xm[0] += now[0]
  xm[1] += now[1]
  use = max(xp[0]**2+xp[1]**2,xm[0]**2+xm[1]**2)
  can.append(use)
print(max(can)**.5)

### FIXED CODE ###

a = input()
b = input()
ans = 0
for i in range(3):
  if a[i] == b[i]:
    ans += 1
print(ans)
a,b=list(map(int,input().split())

if a%2==1 and b%2==1:
    print('Yes')
else:
    print('No')



### FIXED CODE ###

a,b=list(map(int,input().split()))

if a*b%2==0:
    print('No')
else:
    print('Yes')
n,m,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
a.reverse()
b.reverse()
ans=0
t=0
while len(a)>0 or len(b)>0:
  if len(a)>0 and a[-1]<b[-1]:
    t+=a.pop()
  elif len(b)>0:
    t+=b.pop()
  if t>k:
    break
  else:
    ans+=1
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
ca=[0]*(n+1)
ca[1]=a[0]
for i in range(n):
  ca[i+1]=ca[i]+a[i]
cb=[0]*(m+1)
cb[1]=b[0]
for i in range(m):
  cb[i+1]=cb[i]+b[i]
j=m
ans=0
for i in range(n+1):
  t=ca[i]
  while j>=0:
    if t+cb[j]>k:
      j-=1
    else:
      ans=max(ans,i+j)
      break
print(ans)
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

x = max(A)
hurui = [x]*(x+1)
for i in range(2, N+1):
    for j in range(i, x, i):
        hurui[j] = min(i, hurui[j])

cnt = Counter()
for i in range(N):
    num = A[i]
    while num > 1:
        x = hurui[num]
        while num%x == 0:
            num //= x
        cnt[x] += 1

a = cnt.most_common(1)[0][1]
if a == 1:
    print("pairwise coprime")
elif a < N:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

x = max(A)
hurui = [x]*(x+1)
for i in range(2, x+1):
    for j in range(i, x+1, i):
        hurui[j] = min(i, hurui[j])

cnt = Counter([1])
for i in range(N):
    num = A[i]
    while num > 1:
        x = hurui[num]
        while num%x == 0:
            num //= x
        cnt[x] += 1

a = cnt.most_common(1)[0][1]
if a == 1:
    print("pairwise coprime")
elif a < N:
    print("setwise coprime")
else:
    print("not coprime")
# -*- coding: utf-8 -*-

a, b, k = map(int, input().split())

if b-a < k*2:
    for i in range(a, b+1):
        print(i)
    exit()

aa = list(range(a, b+1))

bb = []

bb.append(aa[0:k])
bb.append(aa[len(aa)-k:])
bb = sum(bb,[])
bb = sorted(list(set(bb)))
for i in bb:
    print(i)


### FIXED CODE ###

# -*- coding: utf-8 -*-

a, b, k = map(int, input().split())

if b-a < 2*k:
    for i in range(a, b+1):
        print(i)
else:
    for i in range(a, a+k):
        print(i)
    for i in range(b-k+1, b+1):
        print(i)
import math
from fractions import gcd
a, b = map(int, input().split())
g = gcd(a, b)
sqrt = math.floor(g ** 0.5)
factors = [1]
z = g
for i in range(2, sqrt + 1):
    if not z % i:
        factors.append(i)
        while z % i == 0:
            z //= i
if z > 1:
    factors.append(i)
print(len(factors))

### FIXED CODE ###

import math
from fractions import gcd
a, b = map(int, input().split())
g = gcd(a, b)
sqrt = math.floor(g ** 0.5)
factors = [1]
z = g
for i in range(2, sqrt + 1):
    if not z % i:
        factors.append(i)
        while z % i == 0:
            z //= i
if z > 1:
    factors.append(z)
print(len(factors))
dance = input()
judge = True

for i in dance:
  if i % 2 == 0 and dance[i] == "R":
    judge = False
    break
  if i % 2 == 1 and dance[i] == "L":
    judge = False
    break

if judge:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

dance = input()
judge = True

for i in range(len(dance)):
    if i % 2 == 1 and dance[i] == "R":
        judge = False
        break
    if i % 2 == 0 and dance[i] == "L":
        judge = False
        break

if judge:
    print("Yes")
else:
    print("No")
import sys
input = sys.stdin.readline
from math import sqrt

N,K=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

def calcdismax(x,y):
    TIME=[]
    for mx,my,c in M:
        TIME.append(c*sqrt((mx-x)**2+(my-y)**2))

    TIME.sort()

    #print(TIME)

    return TIME[K-1]

def div200(xmin,xmax,ymin,ymax):

    xh=(xmax-xmin)/200
    yh=(ymax-ymin)/200

    MIN=1<<30
    MINx=0
    MINy=0

    for i in range(201):
        xk=xmin+xh*i
        for j in range(201):
            yk=ymin+yh*j
            cd=calcdismax(xk,yk)

            #print(xk,yk,cd)

            if MIN>cd:
                MIN=cd
                MINx=xk
                MINy=yk

    #print(MINx,MINy,MIN)

    return MINx,MINy

now=1010
k=0
l=0
while now>10**(-10):
    k,l=div100(k-now,k+now,l-now,l+now)
    now/=2

print(calcdismax(k,l))


### FIXED CODE ###

import sys
input = sys.stdin.readline
from math import sqrt

N,K=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

def cross_coor(x0,y0,c0,x1,y1,c1): # 二円の交点
    if (c1-c0)**2<=(x1-x0)**2+(y1-y0)**2<=(c0+c1)**2:
        x2,y2=x1-x0,y1-y0
        a=(x2**2+y2**2+c0**2-c1**2)/2

        xa=(a*x2+y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        ya=(a*y2-x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        xb=(a*x2-y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        yb=(a*y2+x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        return [(xa,ya),(xb,yb)]
    else:
        return False

OK=1<<31
NG=0

while OK-NG>10**(-8):
    mid=(OK+NG)/2
    
    CANDI=[]
    for i in range(N):
        x0,y0,c0=M[i]
        CANDI.append((x0,y0))
        for j in range(i+1,N):
            x1,y1,c1=M[j]
            CR=cross_coor(x0,y0,mid/c0,x1,y1,mid/c1)
            if CR:
                CANDI.extend(CR)

    for z,w in CANDI:
        count=0
        for x,y,c in M:
            if (c**2)*((x-z)**2+(y-w)**2)<=(mid+10**(-8))**2:
                count+=1
            
        if count>=K:
            OK=mid
            break
    else:
        NG=mid

print((OK+NG)/2)
aa=int(input())
N=[0 for i in range(aa)]
for i in range(aa):
  bb=input()
  #print(b)
  N[i]=bb.split()




for i in range(aa):

  a=int(N[i][0])
  b=int(N[i][1])
  c=int(N[i][2])
  d=int(N[i][3])

  e=a-a//b*b
  f=d-d//b*b
  

  h=0 #YES=0 NO=1


  if a<b or d<b :
    h=1
  else:

  
    if f!=0 :
      while e<b:
        if e>c :
          h=1
          
        e+=f
        if h=1:
          break
        #print(e)
        #print(f)
  #print("while")
    else:
      if e>c :
        h=1

  

  if h==1:
    print("No")
  else:
    print("Yes")


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

from fractions import gcd

for i in range(n):
    a = C[i][0]
    b = C[i][1]
    c = C[i][2]
    d = C[i][3]
    ng = 0

    e = 0  # 最初に補充が発生する直前の本数
    e0 = a - b
    e1 = ((c - a%b) // b) * b + a%b
    e = min(e0, e1)

    if e < 0 or b > d:
        ng = 1
    else:
        g = gcd(b, d)
        # print(c+1, b-1, g)
        if c+1 <= b-1 and (c - e) // g < (b-1 - e) // g:
            ng = 1

    if ng == 1:
        print("No")
    else:
        print("Yes")
s = input()
k = int(input())

if s[:k] == '1'*k:
  print(1)
else:
  print(s.translate(str.maketrans('','','1'))[0])
  

### FIXED CODE ###

s = list(map(int,list(input())))
k = int(input())

a = 0
i = 0

while a < k:
  a += min(s[i]**70, k)
  i +=1

print(s[i-1])
n, k = map(int, input().split())
p - list(map(int, input().split()))

p = sorted(p, key = int)
print(sum(p[:2]))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int,input().split()))
p = sorted(p, key = int)
print(sum(p[:k]))
def resolve():
	n, m = map(int, input().split())
	w = list()
	for _ in range(m):
		w.append(input())
	w.sort()
	print("".join(w))
resolve()

### FIXED CODE ###

def resolve():
	n, m = map(int, input().split())
	w = list()
	ans = ""
	for _ in range(n):
		w.append(input())
	w.sort()
	for word in w:
		ans += word
	print(ans)

resolve()
n= int(input())
card = input().split(' ')
card = [int(s) for s in card]
min_s = 1000000000000
for i in range(n -1):
    dif  =abs(sum(card[:i+1]) - sum(card[i+1:]))
    if dif  < min_s:
        min_s= dif
    
print(min_s)


### FIXED CODE ###

ab = input().split(' ')
#print(ab)
if int(ab[0])  % 3 == 0 or int(ab[1]) % 3 ==0   or (int(ab[1])+ int(ab[0])) % 3 == 0:
    ans  = 'Possible'

else:
    ans ='Impossible'
    
if (int(ab[0]) + int(ab[1])) <= 3:
    ans= 'Impossible'
print (ans)
#dojkstra (prioroty queue ver.)
import itertools
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1]) #無向グラフのときはon
'''
#入力が0-indexedのとき
    G[at].append([ct,bt])
    G[bt].append([ct,at]) #無向グラフのときはon
'''
#入力が1-indexedのとき

def dijkstra(s):
    d=[inf]*V
    d[s]=0
    q=queue.PriorityQueue()
    q.put([0,s])
    while q.empty()==False:
        dq,v=q.get()
        if d[v]<dq:
            continue
        for i in range(len(G[v])):
            ec, et=G[v][i]
            #print(ec,et)
            if d[et]>d[v]+ec:
                d[et]=d[v]+ec
                q.put([d[et],et])
    return d

dist=[]
for i in range(V):
    dist.append(dijkstra(i))

rperm=n_perm(rlis)

ans=inf
for rperm in itertools.permutations(rlis):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[j]-1][rperm[j+1]-1]
    ans=min(ans,a_tmp)
    
print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline

#dojkstra
import itertools
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

cost=[[inf]*V for i in range(V)]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d

dist=[None] * V
for i in rlis:
    dist[i-1]=dijkstra(i-1)

ans=inf
for rperm in itertools.permutations(rlis):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[j]-1][rperm[j+1]-1]
    ans=min(ans,a_tmp)

print(ans)
a=input()
b=input()
c=input()
def g(x):
  if x=='a':
    if len(a)==0:
      y='A'
    else:
      y=a[0]
      a=a[1:]
  elif x=='b':
    if len(b)==0:
      y='B'
    else:
      y=b[0]
      b=b[1:]
  else:
    if len(c)==0:
      y='C'
    else:
      y=c[0]
      c=c[1:]
  return y
t=g(a[0])
while t!='A' and t!='B' and t!='C':
  t=g(t)
print(t)
  

### FIXED CODE ###

a=input()
b=input()
c=input()
def s(x):
  if len(x)==1:
    return ''
  else:
    return x[1:]
def g(x):
  global a
  global b
  global c
  if x=='a':
    if len(a)==0:
      y='A'
    else:
      y=a[0]
      a=s(a)
  elif x=='b':
    if len(b)==0:
      y='B'
    else:
      y=b[0]
      b=s(b)
  else:
    if len(c)==0:
      y='C'
    else:
      y=c[0]
      c=s(c)
  return y
t=g(a[0])
while t!='A' and t!='B' and t!='C':
  t=g(t)
print(t)
import heapq
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  Ri = root(R, i)
  Rj = root(R, j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(R, i)
T = {}
for i, t in enumerate(list(set(R))):
  T[t] = i
F = [[] for i in T]
for i, r in enumerate(R):
  heapq.heappush(F[T[r]], A[i])
F = [sorted(f) for f in F]
RF = [i for i in range(len(F))]
ans = 0
LF = len(F)
for i in range(LF - 1):
  for f in F:
    if len(list(f)) == 0:
      ans = 'Impossible'
  if ans == 'Impossible':
    break
  f0 = sorted([[heapq.heappop(f), j] for j, f in enumerate(F)])
  ans += f0[0][0] + f0[1][0]
  for f in f0[2:]:
    heapq.heappush(F[f[1]], f[0])
  F[f0[0][1]] = heapq.heapify(list(heapq.merge(F[f0[0][1]], F[f0[1][1]])))
  F.pop(f0[1][1])
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  ri = root(R, i)
  rj = root(R, j)
  if ri <= rj:
    R[rj] = ri
  else:
    R[ri] = rj
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  R[i] = root(R, i)
if N < 2 * (N - M - 1):
  print('Impossible')
elif M == N - 1:
  print(0)
else:
  cnt= 0
  E = N - M - 2
  C = [0] * N
  F = sorted([[a, R[i]] for i, a in enumerate(A)])
  for a, r in F:
    if C[r] == 0:
      C[r] = a
      cnt += a
    elif E > 0:
      cnt += a
      E -= 1
  print(cnt)
import sys

file = sys.argv[1]
lis = open(file, "r").readlines()
lis = map(int, lis)
lis.sort()
lis.reverse()

for height in lis[0:3]:
    print height

### FIXED CODE ###

import sys

file = sys.stdin
lis = file.readlines()
lis = map(int, lis)
lis.sort()
lis.reverse()

for height in lis[0:3]:
    print height
N,D=map(int,input().split())
X=[list(map(int,input().split())) for i in range(N)]
c=0
for i in range(N-1):
    for j in range(i+1,N):
        c += (sum((a-b)**2) for a,b in zip(X[i],X[j]))**0.5.is_integer()
print(c)

### FIXED CODE ###

N,D=map(int,input().split())
X=[list(map(int,input().split())) for i in range(N)]
c=0
for i in range(N-1):
    for j in range(i+1,N):
        c += (sum((a-b)**2 for a,b in zip(X[i],X[j]))**0.5).is_integer()
print(c)
N,K,X,Y=map(int,input().split())

if N >= K:
  print((N-K)*Y + (K*X))
else:
  print(N*X)

### FIXED CODE ###

N,K,X,Y=[int(input()) for i in range(4)]

if N >= K:
  print(Y*(N-K) + K*X)
else:
  print(N*X)
n = int(input())
a = list(map(int, input().split()))
a = [0] + a + [0]

d_1 = []
for i in range(1, n+2):
  d_1.append(abs(a[i]-a[i-1]))
d_2 = [0]
for i in range(1, n+1):
  d_2.append(abs(a[i+1]-a[i-1]))

s_d = sum(d_1)
for i in range(1, n+1):
  print(s_d - d_1[i] - d_1[i+1] + d_2[i])


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = [0] + a + [0]

d_1 = []
for i in range(1, n+2):
  d_1.append(abs(a[i]-a[i-1]))
d_2 = []
for i in range(1, n+1):
  d_2.append(abs(a[i+1]-a[i-1]))

s_d = sum(d_1)
for i in range(1, n+1):
  print(s_d - d_1[i-1] - d_1[i] + d_2[i-1])
N, L = map(int, input().split())
S = [input() for s in range(L)]
S.sort()
output = ""
for i in S:
  output+=i
prunt(output)

### FIXED CODE ###

n, l = map(int, input().split())
s = sorted(input() for _ in range(n))
print(*s, sep="")
N,M=map(int,input().split())
print(N＊(N-1)/2 +M＊(M-1)/2)


### FIXED CODE ###

N,M=map(int,input().split())
print(N*(N-1)//2+M*(M-1)//2)
xn=input()
p=input()
x,n=xn.split()
if p==' ':
  print(int(x))
else:
  p={int(i) for i in p.split()}
  s={i for i in range(1,100)}
  s_p=list(s-p)
  d=[abs(i-int(x)) for i in s_p]
  print(s_p[d.index(min(d))])

### FIXED CODE ###

xn=input()
x,n=xn.split()
if n=='0':
  print(int(x))
else:
  p=input()
  p={int(i) for i in p.split()}
  s={i for i in range(-150,150)}
  s_p=list(s-p)
  d=[abs(i-int(x)) for i in s_p]
  print(s_p[d.index(min(d))])
import bisect

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	B = [0]
	for i in range(N):
		B.append(B[-1] + A[i])
	#print(B)
	ans = float("inf")
	for i in range(2, N - 1):
		Q = B[i]
		x = bisect.bisect_left(B, Q // 2)
		P = max(B[x], B[1])
		P2 = max(B[x - 1], B[1])
		Q3 = max(B[i] - B[i - 1], B[i] - B[x + 1])
		P3 = Q - Q3
		Q2 = Q - P2
		Q -= P
		S = B[N] - B[i]
		y = bisect.bisect_left(B, (B[i] + B[N]) // 2)
		R = max(B[y] - B[i] , B[i + 1] - B[i])
		R2 = max(B[y - 1] - B[i] , B[i + 1] - B[i])
		S3 = max(B[N] - B[N - 1], B[N] - B[y + 1])
		R3 = S - S3
		S2 = S - R2
		S -= R
		#print(P, Q, R, S)
		#print(sum([P, Q, R, S]))
		ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
		ans = min(ans, max(P2, Q2, R2, S2) - min(P2, Q2, R2, S2))
		ans = min(ans, max(P3, Q3, R3, S3) - min(P3, Q3, R3, S3))
	print(ans)


if __name__ == '__main__':
	main()

### FIXED CODE ###

import bisect

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	B = [0]
	for i in range(N):
		B.append(B[-1] + A[i])
	#print(B)
	ans = float("inf")
	for i in range(2, N - 1):
		Q = B[i]
		x = bisect.bisect_left(B, Q // 2)
		P = max(B[x], B[1])
		P = min(P, B[i - 1])
		if x >= 1:
			P2 = max(B[x - 1], B[1])
			Q2 = Q - P2
		Q3 = max(B[i] - B[i - 1], B[i] - B[x + 1])
		P3 = Q - Q3
		Q -= P

		S = B[N] - B[i]
		y = bisect.bisect_left(B, (B[i] + B[N]) // 2)
		R = max(B[y] - B[i] , B[i + 1] - B[i])
		R = min(R, B[N - 1] - B[i])
		R2 = max(B[y - 1] - B[i] , B[i + 1] - B[i])
		S2 = S - R2
		if y < N:
			S3 = max(B[N] - B[N - 1], B[N] - B[y + 1])
			R3 = S - S3
		S -= R
		ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))
		ans = min(ans, max(P3, Q3, R, S) - min(P3, Q3, R, S))
		ans = min(ans, max(P, Q, R2, S2) - min(P, Q, R2, S2))
		ans = min(ans, max(P3, Q3, R2, S2) - min(P3, Q3, R2, S2))
		if x >= 1:
			ans = min(ans, max(P2, Q2, R, S) - min(P2, Q2, R, S))
			ans = min(ans, max(P2, Q2, R2, S2) - min(P2, Q2, R2, S2))
		if y < N:
			ans = min(ans, max(P, Q, R3, S3) - min(P, Q, R3, S3))
			ans = min(ans, max(P3, Q3, R3, S3) - min(P3, Q3, R3, S3))
		if x >= 1 and y < N:
			ans = min(ans, max(P2, Q2, R3, S3) - min(P2, Q2, R3, S3))
	print(ans)

if __name__ == '__main__':
	main()
while True:
     a=list(map(int, input().split()))
     if a = [0,0]:break
     a.sort()
     print(a[0],a[1])
     


### FIXED CODE ###

while True:
     a,b=map(int, input().split())
     x=[a,b]
     if a ==0 and b==0:break
     x.sort()
     print(x[0],x[1])
input()print(sum(sorted(map(int,input().split()))[1:]))

### FIXED CODE ###

from heapq import heappush, heapreplace

n = int(input())
a = sorted(map(int, input().split()), reverse=True)
h = [-a[0]]
c = 0
for i in range(1, n):
    c += heapreplace(h, -a[i])
    heappush(h, -a[i])
print(-c)
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
tmp = sorted(a)
mx = max(a)
cnt = a.count(mx)

for t in a:
    if t == mx:
        print(tmp[-cnt-1])
    else:
        print(mx)        

### FIXED CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
b = a[:]
mx = max(b)
b.remove(mx)
mx2 = max(b)

for t in a:
    if t == mx:
        print(mx2)
    else:
        print(mx)
x = int(input())

a = 0
while True:
    bmin = (x + a**5)**0.2
    bpls = (x - a**5)**0.2

    if bmin.is_integer():
        print(a,int(bmin))
        break
    elif bpls.is_integer():
        print(a,int(bpls))
        break
    
    a+=1
    print(a)

### FIXED CODE ###

x = int(input())

b = -1
while True:
    b+=1
    amin = (x + b**5)**0.2
    apls = (x - b**5)**0.2

    if isinstance(amin, float):
        amin = round(amin,10)
        if amin.is_integer():
            print(int(amin),b)
            break
    
    if isinstance(apls,float):
        apls = round(apls,10)
        if apls.is_integer():
            print(int(apls),-1*b)
            break