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

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

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

paths = []
for i in range(M):
    paths.append(list(map(int, input().split())))
    paths[-1][0] -= 1
    paths[-1][1] -= 1
    
good = set()
bad = set()

for i in range(N):
    flag = True
    if i in bad:
        continue
    for path in paths:
        if i in path:
            bi = path[0]
            if bi == i:
                bi = path[1]
            if H[i] <= H[bi]:
                bad.add(i)
                flag = False
                break
            else:
                bad.add(bi)
    if flag:
        good.add(i)
        
print(len(good))

### FIXED CODE ###

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

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

paths = []
for i in range(M):
    paths.append(list(map(int, input().split())))
    paths[-1][0] -= 1
    paths[-1][1] -= 1
    
bad = set()

for path in paths:
  if H[path[0]] == H[path[1]]:
    bad.add(path[0])
    bad.add(path[1])
  elif H[path[0]] > H[path[1]]:
    bad.add(path[1])
  else:
    bad.add(path[0])
        
print(N-len(bad))
### BUGGY CODE ###

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

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
ans=[0]*N
#print(ans)
for a in A:
    ans[a-1] += 1
    #print(ans)
for i in ans:
    print(i)
### BUGGY CODE ###

n,m = map(int,input().split())
stair = []
for i in range(m):
    stair.append(int(input()))

ans = [0]*(n+1)
ans[0] = 1
ans[1] = 1
for i in range(n+1):
    if i in stair:
        ans[i] = 0
    else:
        if i ==0 or i==1:
            continue
        else:
            ans[i] = ans[i-2] + ans[i-1]
print(ans[n]%(10**9+7))

### FIXED CODE ###

n,m = map(int,input().split())
ans = [1]*(n+1)
for i in range(m):
    a = int(input())
    ans[a] = 0
    
for i in range(2,n+1):
    if ans[i]==0:
        continue
    else:
        ans[i] = ans[i-2] + ans[i-1]
print(ans[n]%(10**9+7))
### BUGGY CODE ###

import bisect

N=int(input().strip())
L=list(map(int,input().strip().split()))
L.sort()

MAX=L[-1]
count=0
for i,a in enumerate(L[:-2]):
    for  j,b in enumerate(L[i+1:-1]):
        # print(i,j)
        # print(L[i+1:-1])
        minInd=i+1+j+1
        # print(minInd)
        if L[minInd]> a+b:
            continue
        if MAX<a+b:
            count+=N-1-minInd+1
        else:
            ind = bisect.bisect_left(L[minInd:], a+b) # number of < a+b
            count+=ind
        # print(count)
print(count)

### FIXED CODE ###

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

N=int(input())
A = [int(x) for x in input().split()]
S=[]
for i in range(N):
    s=sum(A[i+1:])*A[i]
    S.append(s)
print(sum(S)%(10**9+7))
        


### FIXED CODE ###

N=int(input())
A = [int(x) for x in input().split()]
s=sum(A)
x=0
for i in range(N):
    s=s-A[i]
    x+=s*A[i]    
print(x%(10**9+7))
### BUGGY CODE ###

n,c = list(map(int, input().split()))
W=[]
P=[]
for _ in range(n):
    w,val = list(map(int, input().split()))
    W.append(w)
    P.append(val)
dp=[]
for i in range(n+1):
    dp.append([0]*(c+1))
for i in range(1,n+1):
    for j in range(1,c+1):
        inc=0
        exc=0
        if j-W[i-1]>=0:
            inc=P[i-1]+dp[i-1][j-W[i-1]]
        exc=dp[i-1][j]
        dp[i][j]=max(inc,exc)
print(dp[n][c])

### FIXED CODE ###

n,c = list(map(int, input().split()))
W=[]
P=[]
for _ in range(n):
    w,val = list(map(int, input().split()))
    W.append(w)
    P.append(val)
dp=[]
for i in range(n+1):
    dp.append([0]*(c+1))
for i in range(1,n+1):
    for j in range(1,c+1):
        inc=0
        exc=0
        if j-W[i-1]>=0:
            inc=P[i-1]+dp[i-1][j-W[i-1]]
        exc=dp[i-1][j]
        dp[i][j]=max(inc,exc)
print(dp[n][c])
### BUGGY CODE ###

N, x = map(int, input().split())
A = input().split()
alist = []
count = 0

for i in range(N):
    a = int(A[i])
    alist.append(a)

for ii in range(N - 1):
    if alist[int(ii)] + alist[int(ii) + 1] <= x:
        pass
    else:
        while alist[int(ii)] + alist[int(ii) + 1] > x:
            if alist[int(ii) + 1] > 0:
                alist[int(ii) + 1] -= 1
                count += 1
            else:
                alist[int(ii)] -= 1
                count += 1
            
print(count)


### FIXED CODE ###

N, x = map(int, input().split())
A = input().split()
alist = []
count = 0

for i in range(N):
    a = int(A[i])
    alist.append(a)

for ii in range(N - 1):
    if alist[int(ii)] + alist[int(ii) + 1] <= x:
        pass
    else:
        while alist[int(ii)] + alist[int(ii) + 1] > x:
            if alist[int(ii) + 1] > 0:
                k = alist[int(ii)] + alist[int(ii) + 1] - x
                if k <= alist[int(ii) + 1]:
                    alist[int(ii) + 1] -= k
                    count += k
                else:
                    alist[int(ii)] -= k - alist[int(ii) + 1]
                    alist[int(ii) + 1] = 0
                    count += k
            
print(count)
### BUGGY CODE ###

def main():

    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0]*(K+1) for i in range(N+1)]
    import collections
    mod = 10**9 + 7
    # dp[i][j] i人目まで配って、残りがj個の方法の数
    s = [1]*(K+2)
    s[-1] = 0
    tmp = 0
    for i in range(1, N+1):
        next = [0]*(K+2)
        for j in range(K, -1, -1):
            tmp = s[j] - s[min(K, j+a[i-1]) + 1]
            tmp %= mod
            dp[i][j] = tmp
            next[j] = (next[j+1]+tmp) % mod
        s = list(next)

    print(tmp)


main()


### FIXED CODE ###

def main():

    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0]*(K+1) for i in range(N+1)]
    import collections
    dp[0][K] = 1
    mod = 10**9 + 7
    # dp[i][j] i人目まで配って、残りがj個の方法の数
    for i in range(1, N+1):
        tmp = 0
        q = collections.deque()
        for j in range(K, -1, -1):
            while(q):
                if q[0][0] > j:
                    t = q.popleft()
                    tmp -= t[1]
                else:
                    break
            if dp[i-1][j]:
                tmp += dp[i-1][j]
                q.append((max(j - a[i-1], 0), dp[i-1][j]))
            tmp %= mod
            dp[i][j] = tmp

    print(dp[-1][0])


main()
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
x = sorted(list(map(int, input().split())))
y = sorted(list(map(int, input().split())))
z = sorted(list(map(int, input().split())))
import heapq
shou = 3 * 10**10 + 1
ans = []
heapq.heapify(ans)
for i in range(X-1, -1, -1):
  if len(ans) == K:
    sub = x[i]+y[Y-1]+z[Z-1]
    if sub < shou:
      break
  for j in range(Y-1, -1, -1):
    if len(ans) == K:
      sub = x[i]+y[j]+z[Z-1]
      if sub < shou:
        break
    for k in range(Z-1, -1, -1):
      sub = x[i]+y[j]+z[k]
      if len(ans) < K:
        heapq.heappush(ans, sub)
        shou = min(shou, sub)
      else:
        if sub < shou:
          break
        else:
          heapq.heappush(ans, sub)
          show = heapq.heappop(ans)
ans = list(map(lambda x: x*(-1), ans)) 
heapq.heapify(ans)
for i in range(len(ans)):
  print(heapq.heappop(ans)*(-1))

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
x = sorted(list(map(int, input().split())))
y = sorted(list(map(int, input().split())))
z = sorted(list(map(int, input().split())))


import heapq
ans = []
for i in range(X-1, -1, -1):
  for j in range(Y-1, -1, -1):
    for k in range(Z-1, -1, -1):
      if (X-i)*(Y-j)*(Z-k) <= K:
        sub = x[i]+y[j]+z[k]
        ans.append(sub)
      else:
        break
ans = list(map(lambda x: x*(-1), ans)) 
heapq.heapify(ans)
for i in range(K):
  print(heapq.heappop(ans)*(-1))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
count=0

for i in range(1,n+1):
  for j in a:
    if i==j:
      count+=1
    else:
      break
  del a[:count]
        
  print(count)
  count=0

### FIXED CODE ###

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

for i in a:
  ls[i-1]+=1
for i in ls:
  print(i)
### BUGGY CODE ###

#142
n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(1,n+1):
    print(str(a.index(i)+1)+' ', end="")


### FIXED CODE ###

#142改
n = int(input())
a = list(map(int, input().split()))
b = [0]*n

for i in range(n):
    b[a[i]-1] += i+1
    
for i in range(n):
    print(str(b[i])+' ', end="")
### BUGGY CODE ###

def main():
  k, q = map(int, input().split())
  d = tuple(map(int, input().split()))
  from collections import deque
  from itertools import islice
  for i in range(q):
    n, x, m = map(int, input().split())
    x %= m
    d_mod = deque()
    for i in d:
      i_mod = i % m
      if i_mod == 0:
        d_mod.append(m)
      else:
        d_mod.append(i_mod)
    d_mod_sum = sum(d_mod)
    rep = (n-1) // k
    rem = (n-1) % k
    rem_sum = sum(islice(d_mod, 0, rem))
    ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
    print(ans)
if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  import numpy as np
  k, q = map(int, input().split())
  d = np.array(list(map(int, input().split())))
  for i in range(q):
    n, x, m = map(int, input().split())
    x %= m
    d_mod = d % m
    zero_d = k - np.count_nonzero(d_mod)
    d_mod_sum = np.sum(d_mod) + m * zero_d
    rep = (n-1) // k
    rem = (n-1) % k
    zero_rem = len(d_mod[:rem]) - np.count_nonzero(d_mod[:rem])
    rem_sum = np.sum(d_mod[:rem]) + m * zero_rem
    ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
    print(ans)
if __name__ == '__main__':
  main()
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    MAX = 10**9+7

    n = int(input())
    a = tuple(map(int, input().split()))

    dic = {key:0 for key in range(61)}
    for i in a:
        for ind, j in enumerate(bin(i)[:1:-1]):
            dic[ind] += int(j)

    ans = 0
    bit = 1
    for i in range(61):
        ans += bit * dic[i] * (n-dic[i])
        bit *= 2
    print(ans%MAX)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    MAX = 10**9+7

    n = int(input())
    a = tuple(map(int, input().split()))

    li = [0]*61
    for i in a:
        for j in range(61):
            li[j] += i&1
            i >>= 1
    ans = 0
    bit = 1
    for i in li:
        ans += bit * i * (n-i)
        bit <<= 1
    print(ans%MAX)

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

n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[[i] for i in range(n)]
rail=[[i] for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].append(s)
    rail[s].append(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(road[tmp])
        road[i].extend(road[tmp])
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(rail[tmp])
        rail[i].extend(rail[tmp])
    for j in rail[i]:
        rail[j]=rail[i]
ans=[]
for i,j in zip(road,rail):
    ans.append(str(len(set(i)&set(j))))
print(" ".join(ans))

### FIXED CODE ###

n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[{i} for i in range(n)]
rail=[{i} for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].add(q)
    road[q].add(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].add(s)
    rail[s].add(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(road[tmp])
        road[i].update(road[tmp])
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(rail[tmp])
        rail[i].update(rail[tmp])
    for j in rail[i]:
        rail[j]=rail[i]
ans=[0]*n
for i in range(n):
    if ans[i]!=0:
        continue
    sumset=road[i]&rail[i]
    for j in sumset:
        ans[j]=str(len(sumset))
print(" ".join(ans))
### BUGGY CODE ###

n = int(input())
l = [list(input()) for i in range(n)]
l = ["".join(sorted(i)) for i in l]
l = [i for i in l if i != 1]
l.sort()
s = 0
for i in range(len(l)-1):
  for j in range(i+1,len(l)):
    if l[i] == l[j]:
      s += 1
    else:
      break
print(s)


### FIXED CODE ###

import collections
n = int(input())
s = ["".join(sorted(input())) for i in range(n)]
l = collections.Counter(s)
ans = sum(i*(i-1)//2 for i in l.values())
print(ans)
### BUGGY CODE ###

import heapq

n,m=map(int,input().split())
mm=10**5+5
c=[[0] for i in range(mm)]

for i in range(n):
  a,b=map(int,input().split())
  c[a].append(b)

#print(c)

ans=0
h=[]
for i in reversed(range(m)):
  d=m-i
  h+=list(map(lambda x:-x, c[d]))
  heapq.heapify(h)
  ans+=-heapq.heappop(h)

print(ans)

### FIXED CODE ###

import heapq

n,m=map(int,input().split())
mm=10**5+5
c=[[0] for i in range(mm)]

for i in range(n):
  a,b=map(int,input().split())
  c[a].append(b)

#print(c)

ans=0
h=[]
for i in reversed(range(m)):
  d=m-i
  for j in c[d]:
    heapq.heappush(h,-j)
  #heapq.heapify(h)
  ans+=-heapq.heappop(h)

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

import sys

s = str(sys.stdin.readline())
o = len(s)
while True:
    p1 = s.find("01")
    p2 = s.find("10")
    if p1 == -1 and p2 == -1:
        break
    elif p1 != -1 and p2 != -1:
        i = p1 if p1 < p2 else p2      
    elif p1 == -1:
        i = p2
    elif p2 == -1:
        i = p1

    s = s[:i] + s[i + 2:]
    
print(o - len(s))

### FIXED CODE ###

import sys

s = str(sys.stdin.readline())
c0 = s.count('0')
c1 = s.count('1')
r = c0 if c0 < c1 else c1
print(r*2)
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]
def dou(X):
    n=len(X)
    ma=len(X)-1
    mi=0
    while ma-mi>1:
        mid = (ma + mi)//2
        a=X[n-1]-X[mid]
        b=X[mid-1]-X[0]
        if a>b:
            mi=mid
        else:
            ma=mid
        #print(ma,mi)
    return [X[mi]-X[0],X[n-1]-X[mi]]
num=10**14
for i in range(2,N-1):
    K=A[:i+1]
    L=A[i:]
    #print(K,L)
    ans=[]
    ans=ans+dou(K)+dou(L)
    #print(ans)
    num=min(num,abs(max(ans)-min(ans)))
print(num)

### FIXED CODE ###

from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]
def dou(i,j):
    ma=j
    mi=i
    while ma-mi>1:
        mid = (ma + mi)//2
        a=A[j]-A[mid]
        b=A[mid-1]-A[i]
        if a>b:
            mi=mid
        else:
            ma=mid
        #print(ma,mi)
    return [A[mi]-A[i],A[j]-A[mi]]
num=10**14
for i in range(2,N-1):
    ans=[]
    ans+=dou(0,i)
    ans+=dou(i,N)
    #print(ans)
    t=max(ans)-min(ans)
    num=min(num,t)
print(num)
### BUGGY CODE ###

#! python3
# coding:utf-8

n = int(input())
for i in range(1,n+1):
    cnt=0

    for x in range(1,n+1):
        if x > i:
            continue
        for y in range(1,n-x+1):
            for z in range(1,n-x-y+1):
                eq = x**2 + y**2 + z**2 + x*y + y*z + z*x
                   
                if eq == i:
                    cnt+=1
    print(cnt)

### FIXED CODE ###

#! python3
# coding:utf-8
 
def main():
    n = int(input())
    ans = [0 for _ in range(n)]
    for x in range(1,100):
        for y in range(1,100):
            for z in range(1,100):
                eq = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if eq < n+1:
                    ans[eq-1]+=1
    for i in ans:   
        print(i)

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

N,X=map(int,input().split())
Lx=list(map(int,input().split()))
Lxabs=[]
for i in Lx:Lxabs.append(abs(i-X))

def gcd(a,b):
    while b:a,b=b,a%b
    return a

def multigcd(List):
    for _ in range(len(List)-1):
        List=[gcd(List[0],List[1])]+List[2:]
    return List

print (multigcd(Lxabs)[0])

### FIXED CODE ###

from functools import reduce
N,X=map(int,input().split())
Lx=list(map(int,input().split()))
Lxabs=[]
for i in Lx:Lxabs.append(abs(i-X))

def gcd(a,b):
    while b:a,b=b,a%b
    return a

def multigcd(List):
    return reduce(gcd,List)
        
print (multigcd(Lxabs))
### BUGGY CODE ###

def m(sum, n):
    for size in range(n, 0, -1):
        for i in range(size, n + 1):
            for j in range(size, n + 1):
                s = sum[i][j] - sum[i - size][j] - sum[i][j - size] + sum[i - size][j - size]
                if s == 0:
                    return size
    return 0

while True:
    n = int(raw_input())
    if n == 0:
        break
    s = [map(int, raw_input().replace('.','0').replace('*','1')) for i in range(n)]
    sum = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            sum[i][j] += s[i - 1][j - 1]
            sum[i][j] += (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1])
    print m(sum, n)

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0:
        break
    s = [raw_input() for i in range(n)]
    dp = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(n):
        for j in range(n):
            if s[i][j] == '.':
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
    print max(map(max, dp))
### BUGGY CODE ###

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

r=[0]*(n+1)
r[0]=1

for i in range(1,n+1):
    if i in a:
        continue
    r[i]=r[i-1]+r[i-2]

print(r[n]%1000000007)


### FIXED CODE ###

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

a=[True]*(n+1)
for i in range(m):
    a[int(input())]=False

r=[0]*(n+1)
r[0]=1

for i in range(1,n+1):
    if not a[i]:
        continue
    r[i]=(r[i-1]+r[i-2])%1000000007

print(r[n])
### BUGGY CODE ###

n=int(input())
xl=[list(map(int,input().split())) for _ in range(n)]
xl.sort(key=lambda x: x[0])
ans=0
for i in range(n):
  xi,li=xl[i]
  cnt=1
  for j in range(n):
    xj,lj=xl[j]
    if xi+li<=xj-lj:
      cnt+=1
      xi=xj
      li=lj
  ans=max(ans,cnt)
print(ans)


### FIXED CODE ###

n=int(input())
xl=[list(map(int,input().split())) for _ in range(n)]
xl.sort(key=lambda x: x[0])
cnt=0
nx,nl=xl[0]
for i in range(1,n):
  x,l=xl[i]
  if nx+nl<=x-l:
    nx=x
    nl=l
  else:
    cnt+=1
    if nx+nl>=x+l:
      nx=x
      nl=l
print(n-cnt)
### BUGGY CODE ###

import bisect
#import time
#start = time.time()

def check(r,g,b):
    ans=0
    for i in range(len(r)):
        G=bisect.bisect_left(g,r[i])
        for j in range(G,len(g)):
            B=bisect.bisect_left(b,g[j])
            ans+=len(b)-B
            if 2*g[j]-r[i] in b:
                ans-=1
    return ans

N=int(input())
S=input()
ans=0
r=[]
g=[]
b=[]

for h in range(N):
    if S[h]=="R":
        r.append(h)
    elif S[h]=="G":
        g.append(h)
    else:
        b.append(h)

ans=check(r,g,b)+check(g,b,r)+check(b,r,g)+check(b,g,r)+check(g,r,b)+check(r,b,g)


print(ans)
#process_time = time.time() - start
#print(process_time)

### FIXED CODE ###

N=int(input())
S=input()
ans=S.count("R")*S.count("G")*S.count("B")
for i in range(N):
    for j in range(i+1,N):
        k=2*j-i
        if k<N and S[k]!=S[i] and S[k]!=S[j] and S[j]!=S[i]:
            ans-=1
print(ans)
### BUGGY CODE ###

N=int(input())
S=input()
SS=[a for a in S]
SS.insert(0,0)
answer=0
for i in range(1,N-1):
    for j in range(i+1,N+1):
        if SS[i]==SS[j]:
            continue
        for k in range(j+1,N+1):
            if i+k==j*2:
                continue
            else:
                if SS[i]!=SS[j] and SS[j]!=SS[k] and SS[k]!=SS[i]:
                    answer+=1
print(answer)


### FIXED CODE ###

N=int(input())
S=input()
SS=[a for a in S]
SS.insert(0,0)
nr=S.count("R")
ng=S.count("G")
nb=S.count("B")
n=0
for i in range(1,N-1):
    for j in range(i+1,N):
        k=j*2-i
        if k<=N :
            if SS[i]!=SS[j] and SS[j]!=SS[k] and SS[k]!=SS[i]:
                n+=1
answer=nr*ng*nb-n
print(answer)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in A:
    ans *= i
if ans > pow(10, 18):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

ans = 1
for i in A:
    ans *= i
    if ans > pow(10, 18):
        ans = -1
        break
print(ans)
### BUGGY CODE ###

n = int(input())

a = []

for i in range(n):
    a.append(int(input()))

for i in range(n):
    tmp = a[:]
    tmp.pop(i)
    print(max(tmp))

### FIXED CODE ###

n = int(input())

a = []

for i in range(n):
    a.append(int(input()))

tmp = a[:]
max1 = max(tmp)
tmp.remove(max1)
max2 = max(tmp)

if(max1 == max2):
    for i in range(n):
        print(max1)
else:
    for i in range(n):
        if(a[i] != max1):
            print(max1)
        else:
            print(max2)
### BUGGY CODE ###

N = int(input())
S = input()
R = []
G = []
B = []
for i in range(N):
    if S[i] == "R":
        R.append(i)
    elif S[i] == "G":
        G.append(i)
    else:
        B.append(i)
s = 0
for i in R:
    for j in G:
        for k in B:
            l = [i,j,k]
            l.sort()
            if l[1] - l[0] != l[2] - l[1]:
                s += 1
print(s)


### FIXED CODE ###

#def main():
#    N = int(input())
#    S = input()
#    R = []
#    G = []
#    B = []
#    for i, s in enumerate(S):
#        if s == "R":
#            R.append(i)
#        elif s == "G":
#            G.append(i)
#        else:
#            B.append(i)
#    s = 0
#    for i in R:
#        for j in G:
#            for k in B:
#                if abs(i-j) != abs(j-k) and abs(i-j) != abs(k-i) and abs(j-k) != abs(k-i):
#                    s += 1
#    print(s)
#if __name__ == '__main__':
#    main()
N = int(input())
S = input()
r = S.count("R")
g = S.count("G")
b = S.count("B")
ans = r*g*b
for i in range(N):
    for j in range(i+1, N):
        k = 2*j -i
        if k >= N:
            continue
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -=1
print(ans)
### BUGGY CODE ###

n = int(input())
S = input()
ans = 0
for d in range(n):
    cnt = 0
    for i in range(n-d):
        if S[i] == S[d+i]:
            cnt += 1
        else:
            cnt = 0
        ans = max(ans, min(cnt, d))
print(ans)


### FIXED CODE ###

n = int(input())
S = input()
ans = 0
for d in range(n):
    cnt = 0
    for i in range(n-d):
        if S[i] == S[d+i]:
            cnt += 1
        else:
            cnt = 0
        ans = max(ans, min(cnt, d))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

def findsum(li):

    for i in range(1,len(li)+1):
        tot[i]=tot[i-1]+li[i-1]
    #print(tot)

def findans(start,end,li):
  global tot
  #print("HI")
  if(start>=end):
    return 0
  if(dp[start][end]!=-1):
    return dp[start][end]
  ans = INF
  for k in range(start,end+1):


      ans=min(findans(start,k,li)+findans(k+1,end,li),ans)
  dp[start][end]=ans+(tot[end+1]-tot[start])
  return dp[start][end]
n=int(input())
li=[int(k) for k in input().split()]
tot=[0]*(len(li)+1)
findsum(li)
dp=[[-1 for i in range(n)]for k in range(n)]
print(findans(0,n-1,li))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

def findsum(li):

    for i in range(1,len(li)+1):
        tot[i]=tot[i-1]+li[i-1]
    #print(tot)

def findans(start,end,li):
  global tot
  #print("HI")
  if(start>=end):
    return 0
  if(dp[start][end]!=-1):
    return dp[start][end]
  ans = INF
  for k in range(start,end):


      ans=min(findans(start,k,li)+findans(k+1,end,li),ans)
  dp[start][end]=ans+(tot[end+1]-tot[start])
  return dp[start][end]
n=int(input())
li=[int(k) for k in input().split()]
tot=[0]*(len(li)+1)
findsum(li)
dp=[[-1 for i in range(n)]for k in range(n)]
print(findans(0,n-1,li))