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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


xs,ys,xt,yt = list(map(int, input().split()))
n = int(input())
xyr = [None]*(n+2)
for i in range(n):
    xyr[i] = tuple(map(int, input().split()))
from itertools import product
ns = [[] for _ in range(n+2)]
s = n
t = n+1
xyr[s] = (xs,ys,0)
xyr[t] = (xt,yt,0)
for i in range(n+2):
  for j in range(i+1,n+2):
    if i<j:
        d = max(0, ((xyr[i][0]-xyr[j][0])**2 + (xyr[i][1]-xyr[j][1])**2)**0.5 - (xyr[i][2]+xyr[j][2]))
        ns[i].append((d,j))
        ns[j].append((d,i))
def dijkstra(start):
    import heapq
    vals = [float("inf")] * (n+2)
    h = [(0, start)] # (距離, ノード番号)
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        if u==t:
            break
        for d, v in ns[u]:
            if vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
vals = dijkstra(s)
ans = vals[t]
print(ans)


### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


xs,ys,xt,yt = list(map(int, input().split()))
n = int(input())
xyr = [None]*(n+2)
for i in range(n):
    xyr[i] = tuple(map(int, input().split()))
from itertools import product
# ns = [[] for _ in range(n+2)]
data = []
rs = []
cs = []
s = n
t = n+1
xyr[s] = (xs,ys,0)
xyr[t] = (xt,yt,0)
for i,j in product(range(n+2), range(n+2)):
    if i<j:
        d = max(0, ((xyr[i][0]-xyr[j][0])**2 + (xyr[i][1]-xyr[j][1])**2)**0.5 - (xyr[i][2]+xyr[j][2]))
        data.append(d)
        rs.append(i)
        cs.append(j)
import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(n+2, n+2))
ans = scipy.sparse.csgraph.dijkstra(m, indices=t, directed=False)
print(ans[s])
### BUGGY CODE ###

n=int(input())
ans=0
a=list(map(int,input().split()))
now=max(a)
noww=now
matc=list(0 for i in range(n+2*now))
mat2=list(0 for i in range(n+2*now))
for i in range(n):
  matc[now-a[i]]+=1
  mat2[now+a[i]]+=1
  now+=1
#print(matc)
for j in range(noww,noww+n+1):
  ans+=matc[j]*mat2[j]
print(ans)
       
       




### FIXED CODE ###

import numpy as np
n=int(input())
ans=0
a=list(map(int,input().split()))
now=max(a)
noww=now
k=n+2*now
matc=[0]*(n+2)
mat2=[0]*(n+2)
for i in range(n):
  neg=i-a[i]
  pos=i+a[i]
  if neg>=0:
    matc[neg]+=1
  if pos<=n:
    mat2[pos]+=1
  now+=1
#print(matc)
for j in range(n+2):
  ans+=matc[j]*mat2[j]
print(ans)
### BUGGY CODE ###

S = input()
T = input()

for n in range(len(S)):
  S = S.translate(str.maketrans({S[n]:T[n],T[n]:S[n]}))
if S == T :
  print("Yes")
else:
  print("No")


### FIXED CODE ###

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    S = SI()
    T = SI()
    
    
    ord_S = [0 for _ in range(26)]
    ord_T = [0 for _ in range(26)]
    
    for n in range(len(S)):
        ord_S[ord(S[n])-97] += 1
        ord_T[ord(T[n])-97] += 1
    
    
    s_ord_S = sorted(ord_S)
    s_ord_T = sorted(ord_T)
    
    for p in range(26):
        if s_ord_S[p] != s_ord_T[p]:
            print("No")
            sys.exit()
    print("Yes")
        

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

range = xrange
input = raw_input
MOD = 10**9+7
 
n = int(input())

dp = [0] * (1 << n)
for i in [i for i, x in enumerate(input().split()) if x == '1']:
    dp[1 << i] = 1

npow = 1 << n

A = [1<<j for j in range(n)]
masks = [[mask for mask in range(npow) if not mask & jpow] for jpow in A]

for i in range(n - 1):
    _dp = [0] * npow
    for j in [i for i, x in enumerate(input().split()) if x == '1']:
        jpow = 1 << j
        for mask in masks[j]:
            _dp[mask ^ jpow] += dp[mask]
    for mask in range(npow):
        _dp[mask] %= MOD
    dp = _dp
 
print(sum(dp) % MOD)

### FIXED CODE ###

range = xrange
input = raw_input
MOD = 10**9+7
 
n = int(input())

dp = [0] * (1 << n)
for i in [i for i, x in enumerate(input().split()) if x == '1']:
    dp[1 << i] = 1

npow = 1 << n

for i in range(n - 1):
    _dp = [0] * npow
    for j in [i for i, x in enumerate(input().split()) if x == '1']:
        jpow = 1 << j
        mask = 0
        while mask < npow:
            _dp[mask + jpow] += dp[mask]
            mask += 1 + ((mask+1) & jpow)
    for mask in range(npow):
        _dp[mask] %= MOD
    dp = _dp
 
print(sum(dp) % MOD)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
A=LI()
MEMO = [[0]*(N+1) for i in range(N+1)]
turn = -1 if N%2 == 0 else 1
for i in range(N): MEMO[i][i+1] = turn*A[i] 

for wid in range(2, N+1):
    turn *= -1
    for i in range(N-wid+1):
        xy1 = MEMO[i+1][i+wid] + turn*A[i]
        xy2 = MEMO[i][i+wid-1] + turn*A[i+wid-1]
        MEMO[i][i+wid] = xy1 if turn*xy1 > turn*xy2 else xy2

print(MEMO[0][N])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
A=LI()
MEMO = [[0]*(N+1) for i in range(N+1)]
turn = -1 if N%2 == 0 else 1
for i in range(N): MEMO[i][i+1] = turn*A[i] 

for wid in range(2, N+1):
    turn *= -1
    for i in range(N-wid+1):
        xy1 = MEMO[i+1][i+wid] + turn*A[i]
        xy2 = MEMO[i][i+wid-1] + turn*A[i+wid-1]
        MEMO[i][i+wid] = xy1 if turn*xy1 > turn*xy2 else xy2

print(MEMO[0][N])
### BUGGY CODE ###

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

def main():
    N ,K  =  [int(i) for i in input().split()]
    As =   [int(i) for i in input().split()]

    rireki = []
    loop = ""

    ind = 1
    #a = As[0]
    while(1):
        if ind in rireki:
            loop = ind
            break
        else:
            rireki.append(ind)
            ind = As[ind-1]
    #print(rireki,loop)
    loop_c = len(rireki) - rireki.index(loop)
    if K <= len(rireki)-1:
        print(rireki[K])
    else:
        nokori = K-len(rireki)+1
        ans = nokori % loop_c
        if ans == 0:
            print(rireki[-1])
        else:
            print(rireki[rireki.index(loop)+ans-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

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

def main():
    N ,K  =  [int(i) for i in input().split()]
    As =   [int(i) for i in input().split()]

    rireki = []
    loop = ""

    ind = 1
    flags = [0 for _ in range(N)]
    while(1):
        if flags[ind-1] == 1:
            loop = ind
            break
        else:
            rireki.append(ind)
            flags[ind-1] = 1
            ind = As[ind-1]

        #print(flags)
    #print(rireki,loop)
    loop_c = len(rireki) - rireki.index(loop)
    if K <= len(rireki)-1:
        print(rireki[K])
    else:
        nokori = K-len(rireki)+1
        ans = nokori % loop_c
        if ans == 0:
            print(rireki[-1])
        else:
            print(rireki[rireki.index(loop)+ans-1])

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

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

for i in range(M):
  A[A.index(max(A))] = max(A)//2
print(sum(A))

### FIXED CODE ###

import heapq
N,M = map(int,input().split())

A = list(map(int,input().split()))
H = []
for i in A:
  heapq.heappush(H, -int(i))
for i in range(M):
  a = heapq.heappop(H)
  heapq.heappush(H, -(-a//2))
print(-sum(H))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N = int(input())
list = []
# 文字列の入力
for i in range(N):
    s = input()
    if not s in list:
        list.append(s)

#print(list)
print(len(list))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
N = int(input())
list = []
# 文字列の入力
for i in range(N):
    s = input()
    list.append(s)
    #if not s in list:
        #list.append(s)

#print(list)
print(len(set(list)))
### BUGGY CODE ###


def ans_dp(H,W,M):
    dp = [[0 for i in range(H*W)] for j in range(H*W)]
    flag = [[0 for i in range(H*W)] for j in range(H*W)]
    if M[0][0] == "#":
        dp[0][0] = 1
        flag[0][0] = 1
    else:
        dp[0][0] == 0
    for i in range(1,W):
        if M[0][i] == "#":
            flag[0][i] = 1
            if flag[0][i-1] == 1:
                dp[0][i] = dp[0][i-1]
            else:
                dp[0][i] = dp[0][i-1] + 1 
        else:##M[0][i] = "."
            dp[0][i] = dp[0][i-1]
    for j in range(1,H):
        if M[j][0] == "#":
            flag[j][0] = 1
            if flag[j-1][0] == 1:
                dp[j][0] = dp[j-1][0]
            else:
                dp[j][0] = dp[j-1][0] + 1 
        else:##M[0][i] = "."
            dp[j][0] = dp[j-1][0]
    
    for i in range(1,H):
        for j in range(1,W):
            if M[i][j] == "#":
                flag[i][j] = 1
                dp[i][j] = min(dp[i-1][j]+int(not flag[i-1][j]),dp[i][j-1]+int(not flag[i][j-1]))
            else:#M[i][j] == "."
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])
    """
    for i in range(H):
        print(dp[i])
    for i in range(H):
        print(flag[i])
    """
    return dp[W-1][H-1]

def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(list(input()))
    print(ans_dp(H,W,M))
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

def ans_dp(H,W,M):
    dp = [[0 for i in range(W)] for j in range(H)]
    flag = [[0 for i in range(W)] for j in range(H)]
    if M[0][0] == "#":
        dp[0][0] = 1
        flag[0][0] = 1
    else:
        dp[0][0] == 0
    for i in range(1,W):
        if M[0][i] == "#":
            flag[0][i] = 1
            if flag[0][i-1] == 1:
                dp[0][i] = dp[0][i-1]
            else:
                dp[0][i] = dp[0][i-1] + 1 
        else:##M[0][i] = "."
            dp[0][i] = dp[0][i-1]
    for j in range(1,H):
        if M[j][0] == "#":
            flag[j][0] = 1
            if flag[j-1][0] == 1:
                dp[j][0] = dp[j-1][0]
            else:
                dp[j][0] = dp[j-1][0] + 1 
        else:##M[0][i] = "."
            dp[j][0] = dp[j-1][0]
    
    for i in range(1,H):
        for j in range(1,W):
            if M[i][j] == "#":
                flag[i][j] = 1
                dp[i][j] = min(dp[i-1][j]+int(not flag[i-1][j]),dp[i][j-1]+int(not flag[i][j-1]))
            else:#M[i][j] == "."
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])
    """
    for i in range(H):
        print(dp[i])
    for i in range(H):
        print(flag[i])
    """
    return dp[H-1][W-1]

def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(list(input()))
    print(ans_dp(H,W,M))
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Fri Apr  5 17:16:14 2019

@author: adachi-lab
"""

input_1 = input()
S = input()
l = []
r = []


N = input_1.split()[0]
Q = input_1.split()[1]

for i in range(int(Q)):
    input_3 = input()
    l.append(int(input_3.split()[0]))
    r.append(int(input_3.split()[1]))

W = [S[x-1:y] for (x, y) in zip(l, r)]
for i in range(len(W)):
    print(W[i].count('AC'))



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Apr  8 10:49:27 2019

@author: adachi-lab
"""


input_1 = input()
S = input()
l = []
r = []

N = input_1.split()[0]
Q = input_1.split()[1]

for i in range(int(Q)):
    input_3 = input()
    l.append(int(input_3.split()[0]))
    r.append(int(input_3.split()[1]))
    
s_1 = []
x = 0
for w in range(len(S)-1):
    if S[w] == 'A' and S[w+1] == 'C':
        x += 1
        s_1.append(x)
    else:
        s_1.append(x)
        
s_1.insert(0,0)
w = []

for j in range(len(l)):
    p = s_1[r[j]-1]-s_1[l[j]-1]
    w.append(p)
    
for t in range(len(w)):
    print(w[t])
### BUGGY CODE ###

from collections import deque
n=int(input())
a=[deque(list(map(int,input().split()))) for _ in range(n)]
ans=0
na={1}
cnt=0
while cnt<(n*(n-1))//2:
  ans+=1
  na=set(())
  for i in range(n):
    if i+1 in na:continue
    if not a[i]:continue
    if a[i] and a[i][0] in na:continue
    if a[a[i][0]-1][0]==i+1:
      na.add(i+1)
      na.add(a[i][0])
      a[a[i][0]-1].popleft()
      a[i].popleft()
      cnt+=1
  if not na:
    print(-1)
    exit()
print(ans)



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
  n=int(input())
  a=[list(map(int,input().split())) for _ in range(n)]
  f=lambda x:((x[0]-1)*(n-1+n-x[0]+1))//2+x[1]-x[0]-1
  m=(n*(n-1))//2
  g=[[] for _ in range(m)]
  for i in range(n):
    for j in range(n-2):
      if i+1>a[i][j]:
        t0=f((a[i][j],i+1))
      else:
        t0=f((i+1,a[i][j]))
      if i+1>a[i][j+1]:
        t1=f((a[i][j+1],i+1))
      else:
        t1=f((i+1,a[i][j+1]))
      g[t0].append(t1)
  def dfs(t):
    if v[t]:
      if c[t]==0:
        return -1
      else:
        return dp[t]
    v[t]=1
    for l in g[t]:
      ret=dfs(l)
      if ret==-1:return -1
      dp[t]=max(dp[t],ret+1)
    c[t]=1
    mi.discard(t)
    return dp[t]
  ans=0
  v=[0]*m
  c=[0]*m
  dp=[0]*m
  #print(g)
  mi=set(list(range(m)))
  while mi:
    i=mi.pop()
    tmp=dfs(i)
    if tmp==-1:
      print(-1)
      exit()
    ans=max(ans,tmp)
    #print(dp)
  print(ans+1)

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

import bisect

N, M = map(int, input().split())

A = list(map(int, input().split()))
A.sort()
#print(A)

for _ in range(M):
    a = int(A.pop()/2)
    bisect.insort_left(A, a)

print(sum(A))

### FIXED CODE ###

import heapq #今回は優先度キューを使う

N, M = map(int, input().split())

A = list(map(lambda x:-int(x), input().split())) #優先度付きキューは最小値しか出せないので、×-1して最大値を最小値にしている
#A.sort() 今回は間に合わない
heapq.heapify(A) #優先度付きキューに変換
#print(A)

for _ in range(M):
    a = heapq.heappop(A) #最小値取得
    a = -a // 2 #負のまま計算すると切り捨てが違うところで起こる
    heapq.heappush(A,-a) #優先度付きキューに挿入

print(-sum(A))
### BUGGY CODE ###

N = int(input())
S = input()

count=[0]*(len(S)+1)
for i in range(len(S)+1):
    count[i]=(S[:i].count('#')+S[i:].count('.'))

print(min(count)) 

### FIXED CODE ###

N = int(input())
S = input()

count = [0]*(len(S)+1)
count[0] = S.count('.')
for i in range(1, len(S)+1):
    count[i] = count[i-1] + (1 if S[i-1]=='#' else 0) - (1 if S[i-1]=='.' else 0)

print(min(count))
### BUGGY CODE ###

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

ans = 0
d.sort()

for k in range(n):
	abc = d[0:k]
	arc = d[k:n]
	if len(abc) == len(arc):
		ans = d[k] - d[k-1] 
print(ans)

### FIXED CODE ###

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

ans = 0
d.sort()

abc = d[0:n//2]
arc = d[n//2:n]
if len(abc) == len(arc):
	ans = d[n//2] - d[n//2-1] 
print(ans)
### BUGGY CODE ###

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


n, m = map(int, input().split())
p = list(map(int, input().split()))

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

### FIXED CODE ###

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x]) #xをxの根に直接つなぐ
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			st1 = self.table[s1]
			st2 = self.table[s2]
			if st1 > st2:
				self.table[s2] = s1
			elif st1 < st2:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


n, m = map(int, input().split())
p = list(map(int, input().split()))

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

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

n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd = [[0 for _ in range(W+1)] for k in range(n+1)]

for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
mw=min(wr)
def maxv(i,w):
	if dd[i][w]!=0:
		
		return dd[i][w]
	if i==n:
		return 0
	if W-w<mw:
		return 0
	if w+wr[i]<=W:
		a=vr[i]+maxv(i+1,w+wr[i])
	else:
		a=0
	b=maxv(i+1,w)
	c=max(a,b)
	dd[i][w]=c
	return c
print(maxv(0,0))



### FIXED CODE ###

n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])
### BUGGY CODE ###

s = input()
x, y = map(int, input().split())

mv = [len(e) for e in s.split("T")]
mv_x = mv[2::2]
mv_y = mv[1::2]


def solve_dp(li, start, end):
    l = len(li)
    mx = sum(li)

    if l == 0:
        return start == end

    left = start - mx
    right = start + mx

    if end > right or end < left:
        return 0

    dp = [[0] * (2 * mx + 1) for _ in range(l + 1)]
    dp[0][start] = 1
    for i, e in enumerate(li, 1):
        for j in range(left, right + 1):
            if left <= j - e <= right:
                dp[i][j] |= dp[i-1][j-e]
            if left <= j + e <= right:
                dp[i][j] |= dp[i-1][j+e]

    return dp[l][end]


bl_x = solve_dp(mv_x, mv[0], x)
bl_y = solve_dp(mv_y, 0, y)

if bl_x and bl_y:
    ans = "Yes"
else:
    ans = "No"

print(ans)


### FIXED CODE ###

s = input()
x, y = map(int, input().split())

mv = [len(e) for e in s.split("T")]
mv_x = mv[2::2]
mv_y = mv[1::2]


def solve_dp(li, start, end):
    l = len(li)
    mx = sum(li)

    if l == 0:
        return start == end

    left = start - mx
    right = start + mx

    if end > right or end < left:
        return 0

    dp = [[0] * (2 * mx + 1) for _ in range(l + 1)]
    dp[0][start] = 1
    for i, e in enumerate(li, 1):
        for j in range(left, right + 1):
            if left <= j - e <= right:
                dp[i][j] |= dp[i-1][j-e]
            if left <= j + e <= right:
                dp[i][j] |= dp[i-1][j+e]

    return dp[l][end]


bl_x = solve_dp(mv_x, mv[0], x)
bl_y = solve_dp(mv_y, 0, y)

if bl_x and bl_y:
    ans = "Yes"
else:
    ans = "No"

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

# coding: utf-8
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()

def min_max(arr):
    """リストの中を二つに分けて、総和の小さい方と大きい方を返す"""
    left = 0; right = len(arr)-1
    l_total = arr[left]
    r_total = arr[right]
    while left + 1 < right:
        if l_total <= r_total:
            left += 1
            l_total += arr[left]
        else:
            right -= 1
            r_total += arr[right]
    mi, ma = min(l_total, r_total), max(l_total, r_total)
    return mi, ma

answer = 10 ** 15
mid = N // 2
used = set([0, 1, N-1])

def F(l, mid, r):
    global answer, used
    used.add(mid)
    l_min, l_max = min_max(A[:mid])
    r_min, r_max = min_max(A[mid:])
    temp = max(l_max, r_max) - min(l_min, r_min)
    if temp < answer:
        answer = temp
    if l_min <= r_min:
        m = (mid+r)//2
        if m not in used:
            F(mid, m, r)
    else:
        m = (mid+l)//2
        if m not in used:
            F(l, m, mid)
    if l_max >= r_max:
        m = (mid+l)//2
        if m not in used:
            F(l, m, mid)
    else:
        m = (mid+r)//2
        if m not in used:
            F(mid, m, r)

F(0, mid, N-1)
print(answer)
# 08

### FIXED CODE ###

# coding: utf-8
import sys
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
Acum = list(accumulate(A))
l_cut = [None] * N  # 左のリストで2つに切り分けるindex
l_cut[1] = 0
l = A[0]; r = A[1]
for i in range(2, N):
    r += A[i]
    diff = abs(r-l)
    index = l_cut[i-1]
    while index < i - 1:
        temp = abs(l + A[index+1] - (r - A[index+1]))
        if temp < diff:
            index += 1
            l += A[index]
            r -= A[index]
            diff = temp
        else:
            break
    l_cut[i] = index

r_cut = [None] * N
r_cut[-2] = N-2
l = A[-2]; r = A[-1]
for i in range(N-3, 0, -1):
    l += A[i]
    diff = abs(r-l)
    index = r_cut[i+1]
    while index > i:
        temp = abs(r + A[index] - (l - A[index]))
        if temp < diff:
            index -= 1
            r += A[index+1]
            l -= A[index+1]
            diff = temp
        else:
            break
    r_cut[i] = index

answer = 10 ** 17
for i in range(1, N-2):
    a = Acum[l_cut[i]]
    b = Acum[i] - a
    c = Acum[r_cut[i+1]] - Acum[i]
    d = Acum[-1] - (a + b + c)
    temp = max(a, b, c, d) - min(a, b, c, d)
    if temp < answer:
        answer = temp

print(answer)
# 27r
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sorted([a[i] - b[i] for i in range(n)])
k = sum(x < 0 for x in c)

if sum(c) < 0:
  print(-1)
elif k == 0:
  print(0)
else:
  for i in range(n):
    if sum(c[len(c) - 1 - i:]) >= -sum(c[:k]):
      print(k + i + 1)
      break

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sorted([a[i] - b[i] for i in range(n)])
k = sum(x < 0 for x in c)
neg = -sum(c[:k])
pos = c[len(c) - 1]

if sum(c) < 0:
  print(-1)
elif k == 0:
  print(0)
else:
  for i in range(n):
    if pos >= neg:
      print(k + i + 1)
      break
    else: pos += c[len(c) - 2 - i]
### BUGGY CODE ###

N = int(input())
L = []
for n in range(N):
  s = str(input())
  if s not in L:
    L.append(s)
print(len(L))

### FIXED CODE ###

N = int(input())
L = []
for n in range(N):
    L.append(str(input()))
L = sorted(L)
#print(L)
ans = 1
for i in range(N-1):
    if L[i] != L[i+1]:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
l1 = list(map(int,input().split()))
m = int(input())
l2 = list(map(int,input().split()))

for i in range(m):
    if l2[i] in l1:
        l1.remove(l2[i])
    else:
        print('NO')
        break
else:
    print('YES')

### FIXED CODE ###

from collections import Counter

n = int(input())
l1 = list(map(int,input().split()))
l1_cnt = Counter(l1) 

m = int(input())
l2 = list(map(int,input().split()))
l2_cnt = Counter(l2) 
l2_set=set(l2)

for i in l2_set:
    if l2_cnt[i]<=l1_cnt[i]:
        continue
    else:
        print('NO')
        break
else:
    print('YES')