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

import heapq
q = []
heapq.heapify(q)

n = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

zeros = [False]*n
Cs = [Bs[(i-1)%n]+Bs[(i+1)%n] for i in range(n)]
Ds = [b-(c+a) for b,c,a in zip(Bs,Cs,As)]
# Dが大きい順に操作していく？
# 初期値
for i,d in enumerate(Ds):
    if d < 0: continue
    heapq.heappush(q,(-d,i))

# print("init",Bs,Cs)
cnt = 0
while len(q) > 0:
    d,i = heapq.heappop(q)
    # 自分と周りの影響を更新
    Bs[i%n] -= Cs[i%n]
    Cs[(i-1)%n] = Bs[(i-2)%n]+Bs[i%n]
    Cs[(i+1)%n] = Bs[(i+2)%n]+Bs[i%n]
    # 周りとの差
    d_m = Bs[(i-1)%n]-Cs[(i-1)%n]-As[(i-1)%n] 
    d_p = Bs[(i+1)%n]-Cs[(i+1)%n]-As[(i+1)%n]
    d_ = Bs[i%n] - Cs[i%n] - As[i%n]
    # print("pop",d,i,d_m,d_p)
    if d_ >= 0:
        heapq.heappush(q,(-d_,i))
    if d_m >= 0:
        heapq.heappush(q,(-d_m,i-1))
    if d_p >= 0:
        heapq.heappush(q,(-d_p,i+1))        
    # print("debug",Bs,Cs)
    cnt += 1
if As == Bs:
    print(cnt)
else:
    print(-1)

### FIXED CODE ###

import heapq
q = []
heapq.heapify(q)

n = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

zeros = [False]*n
Cs = [Bs[(i-1)%n]+Bs[(i+1)%n] for i in range(n)]
# Dが大きい順に操作していく
for i, (b,c,a) in enumerate(zip(Bs,Cs,As)):
    d = b-(c+a) 
    if d < 0: continue
    heapq.heappush(q,(-d,i))

cnt = 0
while len(q) > 0:
    d,i = heapq.heappop(q)
    # 自分と周りの影響を更新
    cnt_ = (Bs[i%n]-As[i%n]) // Cs[i%n]
    Bs[i%n] -= cnt_*Cs[i%n]    
    Cs[(i-1)%n] = Bs[(i-2)%n]+Bs[i%n]
    Cs[(i+1)%n] = Bs[(i+2)%n]+Bs[i%n]
    # 周りとの差
    d_m = Bs[(i-1)%n]-Cs[(i-1)%n]-As[(i-1)%n] 
    d_p = Bs[(i+1)%n]-Cs[(i+1)%n]-As[(i+1)%n]
    if d_m >= 0:
        heapq.heappush(q,(-d_m,i-1))
    if d_p >= 0:
        heapq.heappush(q,(-d_p,i+1))
    cnt += cnt_

if As == Bs:
    print(cnt)
else:
    print(-1)
### BUGGY CODE ###

s = input()
k = int(input())

substring = {}

for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        # print('i={}, j={} s[{}:{}]={}'.format(i,j,i,j,s[i:j]))
        substring[s[i:j]] = True

words = [item[0] for item in substring.items()]
sorted_words = sorted(words)
# print(words)
# print(sorted_words)

# print(substring)

print(sorted_words[k-1])

### FIXED CODE ###

s = input()
k = int(input())

substring = {}

for i in range(len(s)):
    for j in range(i+1, i+1+k):
        # print('i={}, j={} s[{}:{}]={}'.format(i,j,i,j,s[i:j]))
        substring[s[i:j]] = True


words = [item[0] for item in substring.items()]
sorted_words = sorted(words)

print(sorted_words[k-1])
### BUGGY CODE ###

a=int(input())
b=[int(input()) for i in range(a)]
c=[]
for i in range(a):
  d=0
  for j in range(len(c)):
    if b[i]>c[j]:
      d=1
      c[j]=b[i]
      break
  if d==0:
    e=b[i]
    c.append(e)    
print(len(c))

### FIXED CODE ###

a=int(input())
b=[int(input()) for i in range(a)]
LIS = [b[0]]
for i in range(1,len(b)):
  if b[i] <= LIS[-1]:
    LIS.append(b[i])
  else:
    lo=0
    hi=len(LIS)
    while lo < hi:
      mid=(lo+hi)//2
      if b[i]>LIS[mid]:
        hi =mid
      else:
        lo=mid+1  
    LIS[lo] = b[i]
print(len(LIS))
### BUGGY CODE ###

import itertools

N,M,R = map(int,input().split())
Visit = list(map(int,input().split()))
lVisit = len(Visit)

Data = []
INF = 10**10
for _ in range(N):
    Data.append([INF]*N)
for i in range(N):
    Data[i][i] = 0
for _ in range(M):
    a,b,c = map(int,input().split())
    Data[a-1][b-1] = c
    Data[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            Data[i][j] = min(Data[i][j], Data[i][k]+Data[k][j])

ans = 10**10
for course in list(itertools.permutations(Visit)):
    sum1 = 0
    for i in range(lVisit-1):
        to = course[i+1]
        fm = course[i]
        sum1 += Data[fm-1][to-1]
    ans = min(ans,sum1)
print(ans)


### FIXED CODE ###

import itertools

N,M,R = map(int,input().split())
Visit = list(map(int,input().split()))
lVisit = len(Visit)

Data = []
INF = 10**10
for _ in range(N):
    Data.append([INF]*N)
for i in range(N):
    Data[i][i] = 0
for _ in range(M):
    a,b,c = map(int,input().split())
    Data[a-1][b-1] = c
    Data[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            Data[i][j] = min(Data[i][j], Data[i][k]+Data[k][j])

ans = 10**10
for course in list(itertools.permutations(Visit)):
    sum1 = 0
    for i in range(lVisit-1):
        to = course[i+1]
        fm = course[i]
        sum1 += Data[fm-1][to-1]
    ans = min(ans,sum1)
print(ans)
### BUGGY CODE ###

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    from collections import deque
    q = deque()
    p = deque()
    q.append(1)
    buf = 0
    flg = True
    idx = 1
    while flg:
        buf = idx
        idx = a[idx-1]
        if idx in q:
            flg = False
        else:
            q.append(idx)
    for i in range(len(q)):
        tmp = q.pop()
        p.appendleft(tmp)
        if tmp == idx:
            break
    if k < len(q):
        print(list(q)[k%len(q)])
    else:
        k -= len(q)
        print(list(p)[k%len(p)])
    return 0

if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    # k<=10**18 < 2**60
    r = 60
    import math
    r = math.ceil(math.log2(k))
    idx = 0
    a = [a[i]-1 for i in range(n)]
    for i in range(r):
        if (k>>i)&1 == 1:
            idx = a[idx]
        a = [a[a[j]] for j in range(n)]
    print(idx+1)    

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

n, m = map(int, input().split())
P = tuple(map(lambda x:int(x)-1, input().split()))
swaps = [set() for _ in range(n)]
for i in range(m):
    x, y = tuple(map(lambda x:int(x)-1, input().split()))
    swaps[x].add(y)
    swaps[y].add(x)

c = 0
from collections import deque
for idx in range(n):
    q = deque([idx])
    visited = {idx}
    while q:
        i = q.pop()
        if idx == P[i]:
            c += 1
            break
        for s in swaps[i]:
            if not s in visited:
                visited.add(s)
                q.append(s)
print(c)


### FIXED CODE ###

n, m = map(int, input().split())
P = tuple(map(lambda x: int(x)-1, input().split()))
par = list(range(n))
size = [1] * n
def find(x):
    """ 根のノードの値を見つけて返す """
    if x != par[x]:
        par[x] = find(par[x])
    return par[x]

def unite(x, y):
    """xとyを結合する"""
    rootx = find(x)
    rooty = find(y)
    if rootx == rooty:
        return False
    else:
        if size[rootx] < size[rooty]:
            par[rootx] = rooty
            size[rooty] += size[rootx]
        else:
            par[rooty] = rootx
            size[rootx] += size[rooty]
        return True

def same(x, y):
    """ xとyが同じ集合に属しているか """
    return find(x) == find(y)

for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    unite(x, y)
groups = {}
for idx, p in enumerate(par):
    p = find(p)
    groups.setdefault(p, set())
    groups[p].add(idx)

cnt = 0
for k, g in groups.items():
    for gi in g:
        pi = P[gi]
        if pi in g:
            cnt += 1
print(cnt)
### BUGGY CODE ###

from operator import mul
from functools import reduce

mod = 10 ** 9 + 7
def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def pat(n):
  cnt = 0
  for i in range(n//2 + 1):
    cnt += int(combinations_count(n - i, i))
  return cnt

n, m = map(int, input().split())
a = []
start = 0
cnt = 1
for i in range(m):
  ko = int(input())
  end = ko - 1
  cnt = cnt * pat(end - start)
  start = ko + 1
cnt = cnt * pat(n - start)

print(cnt % mod)
  

### FIXED CODE ###

n, m = map(int, input().split())
MOD = 1000000007

fact=[0,1]
fact_inv=[0]*(n+1)
for i in range(2,n+1):
  fact.append(fact[-1]*i % MOD)

fact_inv[n] = pow(fact[n],MOD-2,MOD)
for i in range(n-1,-1,-1):
  fact_inv[i] = fact_inv[i+1]*(i+1)%MOD

def comb(n,r):
  return fact[n]*fact_inv[r]*fact_inv[n-r]%MOD

def sigmaComb(dis):
  ans=0
  if dis == 1 or dis == 0:
    return 1
  end=dis//2+1
  for i in range(end):
    t=comb(dis-i,i)
    #print(dis-i,i,t)
    ans+=t
  return ans

hole=[0]
ans=1
for i in range(m):
  t = int(input())
  availLeft=hole[-1]
  availRight=t-1
  dis=availRight-availLeft
  if dis <0:
    ans=0
    break

  ans=ans*sigmaComb(dis)%MOD
  #print("dis=",dis,t,ans)
  hole.append(t+1)
else:
  availLeft=hole[-1]
  availRight=n
  dis=availRight-availLeft
  #print("dis=",dis,hole[-1],ans)
  ans=ans*sigmaComb(dis)%MOD

print(ans%MOD)
### BUGGY CODE ###

import sys

N = int(input())

A = list(map(int,input().split()))
L = []
R = []
for i in range(N):
  L.append(A[i]+i+1)
  R.append(i+1 - A[i])
L.sort()
R.sort()
i =0
j = 0
cnt = 0
while i<N and j <N:
  if L[i] == R[j]:
    k = j
    while k< N and R[k] == R[j]:
      k += 1
    cnt += k-j
    i += 1
    #j = min(k-1,N-1)
  else:
    if i == N-1:
      j += 1
    elif j == N-1:
      i += 1
    elif L[i] < R[j]:
      i += 1
    else:
      j += 1
print(cnt)

### FIXED CODE ###

import sys
from collections import Counter
N = int(input())

A = list(map(int,input().split()))
L = []
R = []
for i in range(N):
  L.append(A[i]+i+1)
  R.append(i+1 - A[i])
L.sort()
R.sort()
R = Counter(R)

cnt = 0
for i in range(N):
  cnt += R[L[i]]

print(cnt)
### BUGGY CODE ###

n = int(input())
list = [int(x) for x in input().split()]
count = 0
for  i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if not((list[i] >= list[j] + list[k]) or (list[j] >= list[i] + list[k]) or (list[k] >= list[i] + list[j])):
                count+= 1
print(count)



### FIXED CODE ###

from bisect import bisect_left

count = 0
n = int(input())
list = sorted([int(x) for x in input().split()])

for i in range(n):
    for j in range(i + 1, n) :
        sum = list[i] + list[j]
        a = bisect_left(list,sum)
        count += a - j - 1
print(count)
### BUGGY CODE ###

n = int(input())

arr = input().split()
count = 1
if "0" in arr:
  count = 0
else: 
  for i in arr:
    count *= int(i)
  if count > 1000000000000000000: count = -1
  
print(count)


### FIXED CODE ###

n = int(input())
arr = input().split()


def mult():
    if "0" in arr:
        return 0
    else:
        a = 1
        for i in arr:
            a = a * int(i)
            if a > 1000000000000000000:
                return -1
        return a

print(mult())
### BUGGY CODE ###

import sys

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y, z = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)

def main():
    to_check = set(range(1, n+1))
    checked = set()
    cnt = 0
    while to_check:
        stack = [to_check.pop()]
        cnt += 1
        while stack:
            v = stack.pop()
            checked.add(v)
            to_check -= set([v])
            for u in graph[v]:
                if not u in checked:
                    stack.append(u)
    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

### FIXED CODE ###

import sys

n, m, *xyz = map(int, sys.stdin.read().split())
xyz = zip(*[iter(xyz)] * 3)

root = list(range(n+1))
height = [0] * (n + 1)

sys.setrecursionlimit(10**7)
def find_root(v):
    u = root[v]
    if u == v:
        return u
    w = find_root(u)
    root[v] = w
    return w

def unite(u, v):
    ru = find_root(u)
    rv = find_root(v)
    if ru == rv:
        return
    if height[u] >= height[v]:
        root[rv] = ru
        height[ru] = max(height[ru], height[rv] + 1)
    else:
        root[ru] = rv

def main():
    for x, y, z in xyz:
        unite(x, y)
    
    for i in range(1, n+1):
        find_root(i)

    return len(set(root[1:]))

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

#!/usr/bin/env python
# coding: utf-8

# In[19]:


P = int(input())


# In[20]:


# i_list = list(range(1, P+1))
# p_list = i_list[1:]
# p_list.append(i_list[0])

# # print(i_list, p_list)

# ans = 0
# for i in range(P):
#     ans += i_list[i]%p_list[i]
# print(ans)

ans = sum(range(1,P))
print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[21]:


P = int(input())


# In[22]:


# i_list = list(range(1, P+1))
# p_list = i_list[1:]
# p_list.append(i_list[0])

# # print(i_list, p_list)

# ans = 0
# for i in range(P):
#     ans += i_list[i]%p_list[i]
# print(ans)

# ans = sum(range(1,P))
ans = P*(P-1)//2
print(ans)


# In[ ]:
### BUGGY CODE ###

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

A.sort()
F.sort(reverse=True)
AF = [A[i] * F[i] for i in range(N)]

l = -1
r = max(AF)
while l + 1 < r:
    x = (l + r) // 2
    s = sum([max(A[i] - x//F[i], 0) for i in range(N)])
    if s <= K:
        r = x
    else:
        l = x

print(r)

### FIXED CODE ###

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

A.sort()
F.sort(reverse=True)
AF = [A[i] * F[i] for i in range(N)]

l = -1
r = max(AF)
while l + 1 < r:
    x = (l + r) // 2
    s = sum([max(A[i] - x//F[i], 0) for i in range(N)])
    if s <= K:
        r = x
    else:
        l = x

print(r)
### BUGGY CODE ###

N,M = map(int,input().split())
L = [[0] * N for i in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    L[A-1][B-1] = 1
    L[B-1][A-1] = 1
ans = [0] * N
from collections import deque
q = deque()
for i in range(N):
    if L[0][i] == 1:
        ans[i] = 1
        q.append(i)
while True:
    if len(q) == 0:
        break
    else:
        k = q.popleft()
        for i in range(1,N):
            if L[k][i] == 1:
                if ans[i] == 0:
                    ans[i] = k+1
                    q.append(i)
flag = True
for i in range(1,N):
    if ans[i] == 0:
        flag = False
        print('No')
        break
if flag == True:
    print('Yes')
    for i in range(N-1):
        print(ans[i+1])

### FIXED CODE ###

N,M = map(int,input().split())
L = [[] for i in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    L[A-1].append(B-1)
    L[B-1].append(A-1)
ans = [0] * N
visit = [0] * N
visit[0] = 1
from queue import Queue
q = Queue()
q.put(0)
while not q.empty():
    current = q.get()
    for a in L[current]:
        if visit[a] == 0:
            visit[a] = visit[current] + 1
            ans[a] = current + 1
            q.put(a)
        else:
            if visit[a] > visit[current] + 1:
                visit[a] = visit[current] + 1
                ans[a] = current + 1
flag = True
for i in range(1,N):
    if ans[i] == 0:
        flag = False
        print('No')
        break
if flag == True:
    print('Yes')
    for i in range(N-1):
        print(ans[i+1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    edge[x-1].append(y-1)
dp = [-1]*n
    
def calc(x):
    if dp[x] != -1:
        return dp[x]
    if not len(edge[x]):
        dp[x] = 0
        return 0
    dp[x] = max(calc(i) for i in edge[x])+1
    return dp[x]
    
ans = 0
for i in range(n):
    if dp[i] != -1: continue
    ans = max(ans, calc(i))
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    edge[x-1].append(y-1)
dp = [-1]*N

def calc(x):
    if dp[x]!=-1:
        return dp[x]
    if not len(edge[x]):
        dp[x] = 0
        return 0
    dp[x] = max([calc(i) for i in edge[x]])+1
    return dp[x]

ans = 0
for i in range(N):
    if dp[i] != -1: continue
    ans = max(ans, calc(i))
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(input().split())
subordinate = []
for i in range(1,n+1):
    i = str(i)
    count = a.count(i)
    subordinate.append(count)
for j in subordinate:
    print(j)

### FIXED CODE ###

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

N, W = map(int,input().split(' '))
DP = [[None]*(W+1)]*(N+1)
WV = list(tuple(map(int,input().split(' '))) for i in range(N))
DP[0] = [0]*(W+1)
for i in range(0,N):
  DP[i+1] = [None]*(W+1)
  for j in range(0,W+1):
    if WV[i][0] > j:
      DP[i+1][j] = DP[i][j]
    else:
      DP[i+1][j] = max(DP[i][j],DP[i][j-WV[i][0]] + WV[i][1])
print(DP[-1][-1])

### FIXED CODE ###

def DP():
    n,W = map(int, input().split(' '))
    WV = (map(int, input().split(' ')) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(DP())
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a, b, c = 0, 0, 0
L, R = [], []
for p in map(int, input().split()):
  if p < 0:
    a += 1
    L.append(p)
  elif p == 0:
    b += 1
  else:
    c += 1
    R.append(p)
L.sort()
R.sort()
s = a*c
t = b*(b-1)//2 + (a+c)*b
if s < k <= s+t:
  ans = 0
else:
  if k <= s:
    ok = -1
    ng = -(10**18+1)
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = 0
      temp = 0
      for l in L:
        while now < c and l*R[now] > mid:
          now += 1
        temp += c - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  else:
    ok = 10**18
    ng = 0
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = c - 1
      temp = s+t
      for i, r in enumerate(R):
        if now <= i:
          break
        while now > i and r*R[now] > mid:
          now -= 1
        temp += now - i
      now = 0
      for i in range(a-1, -1, -1):
        l = L[i]
        if now >= i:
          break
        while now < i and l*L[now] > mid:
          now += 1
        temp += i - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  ans = ok
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a, b, c = 0, 0, 0
L, R = [], []
for p in map(int, input().split()):
  if p < 0:
    a += 1
    L.append(p)
  elif p == 0:
    b += 1
  else:
    c += 1
    R.append(p)
L.sort()
R.sort()
s = a*c
t = b*(b-1)//2 + (a+c)*b
if s < k <= s+t:
  ans = 0
else:
  if k <= s:
    ok = -1
    ng = -(10**18+1)
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = 0
      temp = 0
      for l in L:
        while now < c and l*R[now] > mid:
          now += 1
        temp += c - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  else:
    ok = 10**18
    ng = 0
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = c - 1
      temp = s+t
      for i, r in enumerate(R):
        if now <= i:
          break
        while now > i and r*R[now] > mid:
          now -= 1
        temp += now - i
      now = 0
      for i in range(a-1, -1, -1):
        l = L[i]
        if now >= i:
          break
        while now < i and l*L[now] > mid:
          now += 1
        temp += i - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  ans = ok
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a_set = sorted(list(set(a)), reverse=True)
cnt, ans, square = 0, 1, 0

for i in range(len(a_set)):
    if a.count(a_set[i]) > 3 and cnt <= 1:
        square = max(square, a_set[i]**2)
    if a.count(a_set[i]) > 1:
        ans *= a_set[i]
        cnt += 1
    if cnt == 2:
        print(max(ans, square))
        exit()

print(0)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = set()
cands = []

for i in a:
    if i in s:
        cands.append(i)
        s.remove(i)
    else:
        s.add(i)

x = sorted(cands, reverse=True)
if len(x) < 2:
    print(0)
else:
    print(x[0]*x[1])
### BUGGY CODE ###

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

l = 0
r = max(A)
m = (r + l) // 2

def cal(N, T, A):
    return max([A[i] - min(A[:i]) for i in range(1,len(A))]) * T // 2

ans = 0
m = cal(N, T, A)
mini = A[0]
for i in range(1, N):
    mini = min((mini, A[i]))
    if m == (A[i] - mini) * T // 2:
        ans += 1
print(ans)



### FIXED CODE ###

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


m = 0
_mini = A[0]
for i in range(1, N):
    _mini = min((_mini, A[i]))
    m = max((m, A[i] - _mini))

ans = 0
mini = A[0]
for i in range(1, N):
    mini = min((mini, A[i]))
    if m == (A[i] - mini):
        ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A_list = [int(item) for item in input().split()]
mini = 2020202020

all_sum = sum(A_list)

j = int(N/2+1)
is_search = True

while is_search:
    if j == 0:
        is_search = False

    F = A_list[:j]
    F_sum = sum(F)
    B_sum = all_sum - F_sum
    delta = B_sum - F_sum
    abs_delta = abs(B_sum - F_sum)
    if abs_delta <= mini:
        mini = abs_delta

    if delta > 0:
        j += int(j / 2)

    elif delta < 0:
        j = int(j / 2)
    else:
        mini = 0
        is_search = False

print(mini)


### FIXED CODE ###

N = int(input())
A_list = [int(item) for item in input().split()]

all_sum = sum(A_list)

F_sum_list = [A_list[0]]

for j in range(1,N):
    F_sum_list.append(F_sum_list[-1] + A_list[j])

delta_list = [abs(all_sum - 2* i) for i in F_sum_list]

print(min(delta_list))
### BUGGY CODE ###

a,b,x = map(int,input().split())
Cnt = 0
for i in range(a,b+1):
	if i%x==0:
		Cnt+=1
print(Cnt)


### FIXED CODE ###

a,b,x = map(int,input().split())
result = b//x - a//x
if a%x == 0:
	result +=1
    
print(result)
### BUGGY CODE ###

N, K = map(int, input().split())
h_list = list(map(int, input().split()))

dp = [float("inf")] * N
dp[0] = 0

for i in range(N):
    for k in range(1, min(K+1, N-i)):
        if dp[i + k] > dp[i] + abs(h_list[i + k] - h_list[i]):
            dp[i + k] = dp[i] + abs(h_list[i + k] - h_list[i])
print(dp[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
h_list = list(map(int, input().split()))

dp = [float("inf") for _ in range(N + 1)]
dp[1] = 0
for i in range(1, N+1):
    for k in range(1, K+1):
        if i + k <= N:
            dp[i+k] = min(dp[i + k], dp[i] + abs(h_list[i-1] - h_list[i-1+k]))

print(dp[N])
### BUGGY CODE ###



N = int(input())
A = list(map(int, input().split()))
infants = []
for i,a in enumerate(A):
    infants.append((a, i))

infants.sort(reverse=True)
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]


# i番目の幼児まで見るとき
for i in range(N):
    """
    i番目の幼児を配置する方法として、
    ・左側の１～i番目として配置
    ・右側の１～i番目として配置
    の方法がある
    
    左のj人目として配置した場合、右にはi-j人配置されていることになる（右も同じ）
    例：５番目を左の二人目として配置したら、右には残りの３人がいる計算になる

    """
    for j in range(i+1):

        # 左側に配置したとき
        dp[j+1][i-j] =    max(dp[j+1][i-j], dp[j][i-j] + infants[i][0] * abs(infants[i][1] - j))
            
        # 右側に配置したとき
        dp[i-j][j+1] = max(dp[i-j][j+1], dp[i-j][j] + infants[i][0] * abs(infants[i][1] - (N-1 - j)))


ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])

print(ans)


### FIXED CODE ###



N = int(input())
A = list(map(int, input().split()))
infants = []
for i,a in enumerate(A):
    infants.append((a, i))

infants.sort(reverse=True)
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]


# i番目の幼児まで見るとき
for i in range(N):
    """
    i番目の幼児を配置する方法として、
    ・左側の１～i番目として配置
    ・右側の１～i番目として配置
    の方法がある
    
    左のj人目として配置した場合、右にはi-j人配置されていることになる（右も同じ）
    例：５番目を左の二人目として配置したら、右には残りの３人がいる計算になる

    """
    for j in range(i+1):

        # 左側に配置したとき
        dp[j+1][i-j] =    max(dp[j+1][i-j], dp[j][i-j] + infants[i][0] * abs(infants[i][1] - j))
            
        # 右側に配置したとき
        dp[i-j][j+1] = max(dp[i-j][j+1], dp[i-j][j] + infants[i][0] * abs(infants[i][1] - (N-1 - j)))


ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])

print(ans)