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

#!/usr/bin/env python3

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

count = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue

        if A[i] % A[j] == 0:
            break

    else:
        count += 1

print(count)


### FIXED CODE ###

#!/usr/bin/env python3

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

A.sort()
A_max = A[-1]
table = [0] * (A_max + 1)

for x in A:
    table[x] += 1
    for y in range(x * 2, A_max + 1, x):
        table[y] += 1

result = sum([1 for x in A if table[x] == 1])
print(result)
### BUGGY CODE ###

from heapq import heappop, heappush


def bfs(x, y):
    path = [float('inf')] * N
    q = []
    heappush(q, (0, x))
    path[x] = 0

    while q:
        s, p = heappop(q)
        for np, d in edge[p]:
            nd = path[p] + d
            if path[np] > nd:
                path[np] = nd
                heappush(q, (nd, np))
    
    return path[y]


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
q = []
for i in range(N):
    for j in range(i + 1, N):
        q.append((A[i][j], i, j))

q.sort()

# B = [[float('inf')] * N for _ in range(N)]

ans = 0
edge = [[] for _ in range(N)]
for a, i, j in q:
    b = bfs(i, j)
    if a < b:
        edge[i].append((j, a))
        edge[j].append((i, a))
        ans += a
    elif a == b:
        pass
    else:
        print(-1)
        exit()

print(ans)


### FIXED CODE ###

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

dp = A
cnt = 0
for i in range(N):
    for j in range(N):
        if all(dp[i][j] < dp[i][k] + dp[k][j] for k in range(N) if k != i and k != j):
            cnt += dp[i][j]
        if any(dp[i][j] > dp[i][k] + dp[k][j] for k in range(N)):
            print(-1)
            exit()

print(cnt // 2)
### BUGGY CODE ###


s = input()
for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        s = s[::-1]
    else:
        if q[1] == '1':
            s = ''.join([q[2], s])
        else:
            s += q[2]
print(s)

### FIXED CODE ###

def main():
    c = 0
    s = input()
    f = ''
    b = ''
    for _ in range(int(input())):
        q = input().split()
        if q[0] == '1':
            c += 1
        else:
            if (q[1] == '1' and c%2 == 0) or (q[1]=='2' and c%2==1):
                f = q[2] + f
            else:
                b += q[2]
    if c % 2 == 0:
        print(f+s+b)
    else:
        print(b[::-1]+s[::-1]+f[::-1])

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

L, R = map(int, input().split())

min = 2*(10**9)+1
for i in range(L, R):
    for j in range(i+1, R+1):
        #print("i, j = {}, {}".format(i, j))
        a = (i*j) % 2019
        if(min >= a):
            min = a

print(min)
#print( (L*R) % 2019)

### FIXED CODE ###

L, R = map(int, input().split())
m = 2*(10**9)+1

R = int(min([R, L+2019*2]))

for i in range(L, R):
    for j in range(i+1, R+1):
        a = (i*j) % 2019
        if(m >= a):
            m = a
print(m)
### BUGGY CODE ###

import copy

def signed_area(p1, p2, p3):
    '''符号付き面積を計算 '''

    area = (((p2[0] - p1[0]) * (p3[1] - p1[1])) - ((p3[0] - p1[0]) * (p2[1] - p1[1]))) / 2
    return area


def convex_hull(p_list):
    '''グラハムの凸包走査 '''

    p_sort = []
    for i in p_list:
        p_sort.append(i[0])

    # x座標が最小のものをリストの先頭に配置。
    min_index = p_sort.index(min(p_sort))
    min_p = p_list.pop(min_index)
    p_list.insert(0, min_p)

    # 座標最小の点と他の点との角度順にソート ソートアルゴリズムに選択の余地が有る。
    p_length = len(p_list)
    count = 0
    index = 0
    while True:
        count += 1
        index += 1

        area_sign = signed_area(p_list[0], p_list[index], p_list[index + 1])

        # 符号付き面積が負ならば点を入れ替え
        if area_sign < 0:
            p_list[index], p_list[index + 1] = p_list[index + 1], p_list[index]
            count = 0

        if count == p_length - 1:
            break

        if index == p_length - 2:
            index = 0

    # 凹部の点を削除する。
    index = -1
    count = 0
    while True:
        index += 1
        count += 1

        area_sign = signed_area(p_list[index], p_list[index + 1], p_list[index + 2])
        if area_sign < 0:
            del p_list[index + 1]
            count = 0

        if count == len(p_list):
            break

        if index >= len(p_list) - 3:
            index = -1
    return p_list



N = int(input())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])

l.sort()
k = copy.deepcopy(l[0])
ll = [k]
for i in range(1,len(l)):
    if k != l[i]:
        ll.append(l[i])
        k = l[i]
if len(ll) == 1:
    print(0)
elif len(ll) == 2:
    print(abs(ll[0][0]-ll[1][0])+abs(ll[0][1]-ll[1][1]))
else:
    F = convex_hull(ll)
    L = len(F)
    ans = 0
    for i in range(L-1):
        for j in range(i+1,L):
            ans = max(ans,abs(F[i][0]-F[j][0])+abs(F[i][1]-F[j][1]))
    print(ans)

### FIXED CODE ###

N = int(input())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])

xlim = []
ylim = []

def cha(a):
    return [a[0]-a[1],a[0]+a[1]]

for i in range(N):
        ylim.append(cha(l[i])[1])
        xlim.append(cha(l[i])[0])

xlim.sort()
ylim.sort()

print(max(xlim[-1]-xlim[0],ylim[-1]-ylim[0]))
### BUGGY CODE ###

k, s = map(int, input().split())
k += 1
count = 0
for x in range(k):
    for y in range(k):
        for z in range(k):
            if x + y + z == s:
                count += 1
print(count)

### FIXED CODE ###

k,s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if z >= 0 and z <= k:
            count += 1
print(count)
### BUGGY CODE ###

# 外周Cメートル
# カウンター上には N 貫の寿司
# i 貫目は中橋くんがいる位置から x_i メートル時計回りに進んだ位置に置かれており、
# v_i キロカロリーの栄養価を持ちます
# 歩く際に 1 メートルあたり 1 キロカロリーを消費

N, C = map(int,input().split())
x=["" for i in range(N)]
v=["" for i in range(N)]


for i in range(N):
    x[i], v[i] = map(int,input().split())

#時計回りの場合の最大
CalR=[0 for i in range(N)]
for i in range(N):
    CalR[i]=sum(v[:i+1])-x[i]

MaxR=[0 for i in range(N+1)]

for i in range(1,N+1):
    if CalR[i-1]>=MaxR[i-1]:
        MaxR[i]=CalR[i-1]
    else:
        MaxR[i]=MaxR[i-1]

#反時計回りの最大
CalL=[0 for i in range(N)]
for i in range(N):
    CalL[i]=sum(v[N-i-1:])-(C-x[N-i-1])

MaxL=[0 for i in range(N+1)]

for i in range(1,N+1):
    if CalL[i-1]>=MaxL[i-1]:
        MaxL[i]=CalL[i-1]
    else:
        MaxL[i]=MaxL[i-1]

#最初時計回りに進んだ場合の答え
AnsR=[0 for i in range(N)]

for i in range(N):
    AnsR[i]=CalR[i]-x[i]+MaxL[N-1-i]

#最初反時計回りに進んだ場合の答え
AnsL=[0 for i in range(N)]

for i in range(N):
    AnsL[i]=CalL[i]-(C-x[N-1-i])+MaxR[N-1-i]

print(max(max(AnsR),max(AnsL),max(CalR),max(CalL),0))

### FIXED CODE ###

N, C = map(int,input().split())
x=["" for i in range(N)]
v=["" for i in range(N)]

for i in range(N):
    x[i], v[i] = map(int,input().split())

#時計回りの場合の最大
CalR=[0 for i in range(N)]
CalR[0]=v[0]-x[0]
for i in range(1,N):
    CalR[i]=CalR[i-1]+v[i]-x[i]+x[i-1]

MaxR=[0 for i in range(N+1)]

for i in range(1,N+1):
    if CalR[i-1]>=MaxR[i-1]:
        MaxR[i]=CalR[i-1]
    else:
        MaxR[i]=MaxR[i-1]

#反時計回りの最大
CalL=[0 for i in range(N)]
CalL[0]=v[N-1]-(C-x[N-1])
for i in range(1,N):
    CalL[i]=CalL[i-1]+v[N-i-1]+x[N-i-1]-x[N-i]

MaxL=[0 for i in range(N+1)]

for i in range(1,N+1):
    if CalL[i-1]>=MaxL[i-1]:
        MaxL[i]=CalL[i-1]
    else:
        MaxL[i]=MaxL[i-1]

#最初時計回りに進んだ場合の答え
AnsR=[0 for i in range(N)]

for i in range(N):
    AnsR[i]=CalR[i]-x[i]+MaxL[N-1-i]

#最初反時計回りに進んだ場合の答え
AnsL=[0 for i in range(N)]

for i in range(N):
    AnsL[i]=CalL[i]-(C-x[N-1-i])+MaxR[N-1-i]

print(max(max(AnsR),max(AnsL),max(CalR),max(CalL),0))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7


def read_valus():
    return map(int, input().split())


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def p(N, a):
    return (a * (N - a)) % mod


def main():
    N = int(input())
    A = read_list()

    num = [0] * 65
    for a in A:
        tmp = a
        for i in range(65):
            if tmp == 0:
                break
            num[i] += tmp % 2
            tmp //= 2

    res = 0
    for i in range(65):
        if num[i] == 0:
            continue

        res = (res + (pow(2, i, mod) * p(N, num[i])) % mod) % mod

    print(res % mod)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7


def read_valus():
    return map(int, input().split())


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def p(N, a):
    return (a * (N - a)) % mod


def main():
    pows = [1] * 66
    for i in range(65):
        pows[i + 1] = (pows[i] * 2) % mod

    N = int(input())
    A = read_list()

    num = [0] * 65
    for a in A:
        tmp = a
        for i in range(65):
            if tmp == 0:
                break
            num[i] += tmp % 2
            tmp //= 2

    res = 0
    for i in range(65):
        if num[i] == 0:
            continue

        res = (res + (pows[i] * p(N, num[i])) % mod) % mod

    print(res % mod)


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

n = int(input())
s = input()
a = s.count("R")
b = s.count("G")
c = s.count("B")
x = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      if {s[i], s[j], s[k]}=={"R", "G", "B"} and i+k == 2*j:
        x += 1
print(a*b*c-x)


### FIXED CODE ###

n = int(input())
s = input()
a = s.count("R")
b = s.count("G")
c = s.count("B")
z = a*b*c
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)
x = 0
for i in R:
  for j in G:
    if 0 <= 2*j-i <= n-1 and s[2*j-i]=="B":
      x+=1
    if 0 <= 2*i-j <= n-1 and s[2*i-j]=="B":
      x+=1
    if (i+j)%2==0 and s[(i+j)//2]=="B":
      x+=1
print(z-x)
### BUGGY CODE ###

x,y,z,k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sorted(map(int, input().split()), reverse=True)

d = []
d_append = d.append
for i in range(x):
    for j in range(y):
        d_append(a[i]+b[j])

d = sorted(d, reverse=True)
d = d[0:min(k,len(d))]
w = len(d)

e = []
e_append = e.append
for i in range(min(k,z)):
    for j in range(min(k,w)):
        e_append(c[i]+d[j])

e = sorted(e, reverse=True)
for f in e[0:k]:
    print(f)


### FIXED CODE ###

x,y,z,k = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
b = sorted(map(int, input().split()), reverse=True)
c = sorted(map(int, input().split()), reverse=True)

d = []
for i in range(min(x,int(k*1.4))):
    for j in range(min(y,int(k*1.4))):
        d.append(a[i]+b[j])

d = sorted(d, reverse=True)
d = d[0:min(k,len(d))]
w = len(d)

e = []
for i in range(min(k,z)):
    for j in range(w):
        e.append(c[i]+d[j])

e = sorted(e, reverse=True)
for f in e[0:k]:
    print(f)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import fractions

N = int(input().rstrip())
As = list(map(int, input().rstrip().split()))


def gcd_list(cur_gcd, numbers):
    res = cur_gcd
    for idx in range(len(numbers)):
        res = fractions.gcd(res, numbers[idx])
    return res


max_gcd = max(As)
if N > 2:
    # i == 0
    others = As[1:]
    max_gcd = gcd_list(max_gcd, others)
    tmp_gcd = As[0]

    # i >= 1
    for i in range(1, N):
        others = As[i + 1:]
        max_gcd = max(gcd_list(tmp_gcd, others), max_gcd)
        tmp_gcd = fractions.gcd(tmp_gcd, As[i])

print(max_gcd)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import fractions

N = int(input().rstrip())
A = [0] + list(map(int, input().rstrip().split())) + [0]

L = [0] * (N + 2)
R = [0] * (N + 2)

for i in range(0, N):
    L[i + 1] = fractions.gcd(L[i], A[i + 1])

for i in range(N, 0, -1):
    R[i] = fractions.gcd(R[i + 1], A[i])

print(max(fractions.gcd(L[i], R[i + 2]) for i in range(0, N)))
### BUGGY CODE ###

from collections import deque
import sys

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

flag = [ [False] * N for i in range(N) ]
crash = [False] * N
cost = [float("-inf")] * N
cost[0] = 0

dic = {}
for i in range(N):
    dic[i] = []

    

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    dic[A].append([B,C-P])

q = deque([0])

cnt = 0

while len(q) > 0:

    now = q.popleft()

    for bc in dic[now]:
    
        b = bc[0]
        c = bc[1]

        #print (now,b,flag[now],crash[now],flag[b],crash[b])

        if b == N-1 and crash[now]:
            print (-1)
            sys.exit()

        if cost[now] + c > cost[b] or crash[now]:


            if flag[now][b] and not crash[b]:

                crash[b] = True

                cost[b] = cost[now] + c

                flag[b] = flag[now].copy()

                for j in range(N):

                    flag[b][j] = flag[now][j]
                flag[b][b] = True
            
                q.append(b)

            elif not flag[now][b]:
                
                cost[b] = cost[now] + c
                crash[b] = crash[now]
                cost[b] = cost[now] + c
                crash[b] = crash[now]

                flag[b] = flag[now].copy()
                    
                flag[b][b] = True

                q.append(b)

    cnt += 1

    if cnt > M*N:
        print (-1)
        sys.exit()

print (max(0,cost[N-1]))
    


### FIXED CODE ###


"""

https://atcoder.jp/contests/abc137/tasks/abc137_e

辺の重みからPを引いておく
→あとはベルマンフォード？

正の閉路探索→むずくね？
閉路があったとしても、増えなきゃあっていい…

→まずゴールにたどり着ける頂点を列挙
→たどり着けない点は無意味なのでremove

→あとはベルマンフォード
"""

import sys
sys.setrecursionlimit(200000)

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

lis = [ [] for i in range(N) ]
rev = [ [] for i in range(N) ]
exist = [False] * N

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append([B , C - P])
    rev[B].append(A)

def dfs(v):

    exist[v] = True
    for nex in rev[v]:
        if not exist[nex]:
            dfs(nex)

dfs(N-1)

dis = [float("-inf")] * N
dis[0] = 0

for i in range(N+1):

    flag = False

    for v in range(N):
        for uc in lis[v]:

            if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
                #print (uc[0] , dis[v] + uc[1])
                dis[uc[0]] = dis[v] + uc[1]
                flag = True

if flag:
    print (-1)
else:
    print (max( 0 , dis[N-1] ))
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = []
for i in range(n):
    s.append(input())
counter = Counter(s)
ansarr = [k for k, v in counter.items() if v == max(counter.values())]
ansarr.sort()
for ans in ansarr:
    print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = []
for i in range(n):
    s.append(input())
counter = Counter(s)
maxnum = max(counter.values())
keys = [k for k, v in counter.items() if v == maxnum]
keys.sort()
for ans in keys:
    print(ans)
### BUGGY CODE ###

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

#"ありうる値"の最大値なので、K枚選択時はa,b,cの順に選択する

card_num = 0 #カード枚数
card_sum = 0 #値の合計

while card_num < k:
    if a > 0:
        card_sum += 1
        a -= 1
    elif b > 0:
        b -= 1
    elif c > 0:
        card_sum -= 1
        c -= 1
    
    card_num += 1

print(card_sum)

### FIXED CODE ###

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

#"ありうる値"の最大値なので、K枚選択時はa,b,cの順に選択する

card_num = 0 #カード枚数
card_sum = 0 #値の合計

#1card*k
if k <= a:
    card_sum = k
#1card*a + 0card*(k-a)
elif k <= a + b:
    card_sum = a
#1card*a + 0card*b + -1card*(k-a-b)
else:
    card_sum = a - (k-a-b)

print(card_sum)
### BUGGY CODE ###

import math
from functools import reduce
 
k = int(input())
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
kotae = 0
for i in range(k):
    a = i + 1
    for j in range(k):
        b = j + 1
        for l in range(k):
            c = l + 1
            koyakusu = gcd(a, b, c)
            kotae += koyakusu
print(kotae)

### FIXED CODE ###

import math
from functools import reduce
 
k = int(input())
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
kotae = 0
for i in range(k):
    a = i + 1
    for j in range(k):
        b = j + 1
        for l in range(k):
            c = l + 1
            koyakusu = gcd(a, b, c)
            kotae += koyakusu
print(kotae)
### BUGGY CODE ###

A, B,C,K = map(int, input().split())

ans = 0

for i in range(A):
  if(K>0):
    ans = ans + 1
    K = K-1
for i in range(B):
  if(K>0):
    ans = ans 
    K = K-1
for i in range(C):
  if(K>0):
    ans = ans - 1
    K = K-1
print(ans)

### FIXED CODE ###

A, B,C,K = map(int, input().split())
if(K<A):
  print(K)
elif(K>A+B):
  print(A - (K-A-B))
else:
  print(A)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
c=0
d=float("INF")
for i in range(n):
    c+=a[i]
    d=min(d,abs(sum(a)-2*c))
print(d)

### FIXED CODE ###

from itertools import accumulate as ac
n=int(input())
a=list(ac(list(map(int,input().split()))))
d=float("INF")
for i in range(n):
    d=min(d,abs(a[-1]-2*a[i]))
print(d)
### BUGGY CODE ###

h = int(input())
ans = 1
i = 1
while True:
    h //= 2
    ans += 2*i
    i += 1+(i-1)
    if h == 1:
        break
        
print(ans)

### FIXED CODE ###

h = int(input())
ans = 1
i = 1
if h == 1:
    print(1)
else:
    while True:
        h //= 2
        ans += 2*i
        i += 1+(i-1)
        if h == 1:
            break

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

n = int(input())
L = sum([list(map(int, input().split())) for i in range(n)], [])
count = 0
next = 0
NG = [1]
while True:
  if L[next] in NG:
    print(-1)
    quit()
  elif L[next] == 2:
    print(len(NG))
    quit()
  else:
    NG.append(L[next])
    next = L[next]-1

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
cur = 1
cnt = 0
while True:
    if cur == 2:
        print(cnt)
        exit()
    elif cnt > n:
        print(-1)
        exit()
    else:
        cur = a[cur - 1]
        cnt += 1
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline


def main():
    n, s = map(int, input().split())
    a = np.array([int(i) for i in input().split()], dtype="int16")
    MOD = 998244353

    dp = np.zeros(s + 1, dtype="int32")
    dp[0] = 1

    for i in a:
        p = np.zeros(s + 1, dtype="int32")
        dp, p = p, dp
        dp += p * 2
        dp %= MOD
        for j in range(s + 1):
            # print(f"{i = }, {j = }, {dp = }, {p = }")
            if (ji := j + i) <= s:
                dp[ji] = (dp[ji] + p[j]) % MOD

    print(dp[s])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline


def main():
    n, s = map(int, input().split())
    A = [int(i) for i in input().split()]

    MOD = 998244353

    dp = np.zeros(s + 1, dtype="int32")
    dp[0] = 1

    for a in A:
        p = (dp * 2) % MOD
        p %= MOD
        p[a:] += dp[:-a]
        dp = p % MOD

    print(dp[s])


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

from collections import deque

S = input()
Q = int(input())

ANS = deque(S)

for _ in range(Q):
    query = input().split(' ')
    if len(query) == 1:
        ANS.reverse()
    else:
        f, c = query[1:]
        if f == '1':
            ANS.appendleft(c)
        else:
            ANS.append(c)

print(''.join(ANS))

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

ANS = deque(S)

rev = 0

for _ in range(Q):
    query = input().split(' ')
    if len(query) == 1:
        rev = rev ^ 1
    else:
        f, c = int(query[1]), query[2]
        if (f - 1) ^ rev:
            ANS.append(c)
        else:
            ANS.appendleft(c)

if rev:
    ANS.reverse()

print(''.join(ANS))
### BUGGY CODE ###

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

N=input()

#約数列挙
def make_divisors(n):
    divisors=[]
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            divisors.append(i)
            if i!=n/i:
                divisors.append(n/i)
    return divisors

def func(a,b):
    return a**5-b**5

L=make_divisors(N)
for yakusu in L:
    for a in range(N):
        b=a-yakusu
        ret=func(a,b)
        if ret==N:
            print a,b
            quit()
        elif N<ret:
            continue


### FIXED CODE ###

N=input()
for a in range(-200,200):
    for b in range(-200,200):
        if a**5-b**5==N:
            print a,b
            quit()
### BUGGY CODE ###

S = input()
l = len(S)
d = {}



ans = 0
for i in range(l):
    m = int(S) % 2019
    if m in d:
        d[m] += 1
    else:
        d[m] = 1
    S = S[1:]

for k, v in d.items():
    if v >= 2:
        ans += int(v * (v-1)/2)
    if k == 0:
        ans += v
print(ans)



### FIXED CODE ###

S = input()
l = len(S)
d = {}

m = 0

ans = 0
for i in range(l):
    m  = (m + int(S[l-1-i]) * pow(10,i,2019)) % 2019
    if m in d:
        d[m] += 1
    else:
        d[m] = 1

for k, v in d.items():
    if v >= 2:
        ans += int(v * (v-1)/2)
    if k == 0:
        ans += v
print(ans)
### BUGGY CODE ###

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

while True:
    n = int(input())
    print(n,':',sep='',end=' ')
    array = []
    count = 0
    while True:
        for i in range(2,n+1):
            if n%i == 0 and i != n:
                array.append(i)
                n = int(n/i)
                break
            if i == n-1:
                count += 1
                break
        if count == 15:
            break
    array.append(n)
    for i in range(len(array)):
        print(array[i],end=' ')
    print('')

### FIXED CODE ###

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

n = int(input())
print(str(n)+':',end='')
array = []
count = 0
while True:
    if n == 999993031:
        break
    for i in range(2,n+1):
        if n%i == 0 and i != n:
            array.append(i)
            n = int(n/i)
            break
        if i == n:
            count += 1
            break
    if count == 24:
        break

array.append(n)
for i in range(len(array)):
    print(' ',array[i],sep = '',end='')
print('')
### BUGGY CODE ###

n=int(input())
a= list(map(int, input().split()))
a+=a
INF=10**12
dp=[[[INF,0] for i in range(2*n+1)] for i in range(2*n+1)]
# dp[i][j][0]: コスト
# dp[i][j][1]:合成したスライムの合計

for i in range(n):
    for l in range(2*n-i):
        r=l+i
        if r==l:
            dp[l][r][1]=a[l]
            dp[l][r][0]=0
        else:
            # 合成の仕方を確定
            for k in range(l,r):
                dp[l][r][0]=min(dp[l][k][1]+dp[k+1][r][1]+dp[l][k][0]+dp[k+1][r][0],dp[l][r][0])
            dp[l][r][1]=dp[l][r-1][1]+a[r]
print(dp[0][n-1][0])

### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline


n=int(input())
a=list(map(int, input().split()))
b=itertools.accumulate(a)
b=[0]+list(b)
dp=[[0]*(n) for i in range(n)]

x=float('inf')
for i in range(n-1,-1,-1):
    for j in range(i+1,n):
        if j>=i+2:
            for k in range(i,j):
                x=min(dp[i][k]+dp[k+1][j],x)
            dp[i][j]=x+(b[j+1]-b[i])
            x=float('inf')
        else:
            dp[i][j]=b[j+1]-b[i]
print(dp[0][-1])