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

# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [input() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)

# 黒の座標
end = []
# 白の座標
start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            end.append((i, j))
        else:
            start.append((i, j))


def mahattan(sy, sx, ey, ex):
    return abs(sy - ey) + abs(sx - ex)


ans = 0

for i, j in start:
    tmp = 10000
    for ey, ex in end:
        tmp = min(tmp, mahattan(i, j, ey, ex))
    ans = max(ans, tmp)

print(ans)


### FIXED CODE ###

# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)

from itertools import product
from collections import deque


# 開始地点
start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            start.append((i, j))


# 探索の準備
mvx = (1, 0, -1, 0)
mvy = (0, 1, 0, -1)
visited = [[False for _ in range(W)] for _ in range(H)]

n_white = W*H
que = deque([(si, sj, 0) for si, sj in start])

for si, sj in start:
    visited[si][sj] = True

# 幅優先探索
while que:
    y, x, cost = que.popleft()
    # 白マスの数の管理
    n_white -= 1
    if n_white == 0:
        ans = cost
        break

    for dy, dx in zip(mvy, mvx):
        y_new, x_new = y + dy, x + dx
        # 探索に含めない条件
        if not (-1 < y_new < H) or not (-1 < x_new < W):
            continue
        if visited[y_new][x_new]:
            continue

        # 探索に追加してあげる
        que.append((y_new, x_new, cost + 1))
        visited[y_new][x_new] = True


print(cost)
### BUGGY CODE ###

import math
import numpy as np


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N, capacity = inputIntList()
    w = [0 for _ in range(N)]
    v = [0 for _ in range(N)]
    for i in range(N):
        w[i], v[i] = inputIntList()

    dp = [[0 for _ in range(capacity + 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(capacity + 1):
            if j < w[i]:
                dp[i + 1][j] = dp[i][j]
            else:

                dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])
            # print(dp)

    return dp[N][capacity]


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import math


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N, capacity = inputIntList()
    w = [0 for _ in range(N)]
    v = [0 for _ in range(N)]
    for i in range(N):
        w[i], v[i] = inputIntList()

    dp = [[0 for _ in range(capacity + 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(capacity + 1):
            if j < w[i]:
                dp[i + 1][j] = dp[i][j]
            else:

                dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])
            # print(dp)

    return dp[N][capacity]


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

# coding: utf-8
def get_ln_inputs():
    return input().split()


def get_ln_int_inputs():
    return list(map(int, get_ln_inputs()))


def main():
    n = get_ln_int_inputs()[0]
    a = get_ln_int_inputs()
    reverse = n % 2 == 0

    result = list()
    for i in range(n):
        ii = len(result) if i % 2 == 1 else 0
        result.insert(ii, a[i])
    
    if reverse:
        result = result[::-1]

    print(" ".join(list(map(str, result))))


main()

### FIXED CODE ###

# coding: utf-8
def get_ln_inputs():
    return input().split()


def get_ln_int_inputs():
    return list(map(int, get_ln_inputs()))


def main():
    n = get_ln_int_inputs()[0]
    a = get_ln_int_inputs()

    ilist = []

    t = n
    while t > 0:
        ilist.append(t)
        t -= 2
    if t == -1:
        t = 2
    else:
        t = 1
    while t < n:
        ilist.append(t)
        t += 2
    
    print(" ".join(str(a[i - 1]) for i in ilist))


main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10 * 9 + 7

flag = True

for i in range((N+1)%2, N, 2):
    if i == 0:
        if A.count(0) != 1:
            flag = False
    elif A.count(i) != 2:
        flag = False
if flag:
    print(2 ** (N//2) % MOD)
else:
    print(0)


### FIXED CODE ###

# 人数分布は一意
import numpy as np
MOD = 10**9 + 7
N = int(input())
A = np.array([int(x) for x in input().split()])

left = np.arange(N)
right = N-1-left
cnt_1 = np.bincount(np.abs(left-right))
cnt_2 = np.bincount(A)

if cnt_1.shape != cnt_2.shape or (cnt_1 != cnt_2).any():
    answer = 0
else:
    answer = pow(2, N//2, MOD)

print(answer)
### BUGGY CODE ###

_ = input()
seq = list(map(int,input().split()))
 
seq1 = seq[::2]
seq2 = seq[1::2]
 
if len(set(seq)) == 1:
    print(min(len(seq1),len(seq2)))
    exit()
    
def count_dictonary(seq):
    ret_dict={}
    for item in seq:
        if item not in ret_dict:
            ret_dict[item] = 1
        else:
            ret_dict[item]+=1
    return ret_dict
 
seq_dict1 = sorted(count_dictonary(seq1).items(),key=lambda x:x[1],reverse=True)
seq_dict2 = sorted(count_dictonary(seq2).items(),key=lambda x:x[1],reverse=True)
 
min_change=len(seq)
for i1, count1 in seq_dict1:
    ch1 = len(seq1) - count1
    if ch1 > min_change:
        continue
    for i2, count2 in seq_dict2:
      ch2 = len(seq2) - count2
      #print(i1,i2,ch1,ch2,ch1+ch2)
      change_ = ch1+ch2
      if(min_change > ch1+ch2):
        min_change = ch1+ch2
            
print(min_change)

### FIXED CODE ###

_ = input()
seq = list(map(int,input().split()))
 
seq1 = seq[::2]
seq2 = seq[1::2]
 
if len(set(seq)) == 1:
    print(len(seq2))
    exit()
    
def count_dictonary(seq):
    ret_dict={}
    for item in seq:
        if item not in ret_dict:
            ret_dict[item] = 1
        else:
            ret_dict[item]+=1
    return ret_dict
 
def modes(counting_dict):
    #(11,2),(2,1),(3,3)
    ret={}
    for item in counting_dict.items():
        no, count = item
        if counting_dict[no] in ret:
            ret[count].append(no)
        else:
            ret[count]=[no]
            
    return ret
 
 
counting1 = count_dictonary(seq1)
counting2 = count_dictonary(seq2)
 
modes1 = sorted(modes(counting1).items(),reverse=True)
modes2 = sorted(modes(counting2).items(),reverse=True)
 
min_change=len(seq)
if modes1[0][1] != modes2[0][1] or len(modes1[0][1]) >=2 or len(modes2[0][1]) >=2:
    min_change = (len(seq1) - modes1[0][0]) + (len(seq2) - modes2[0][0])
else:
    m01=len(seq)
    m10=len(seq)
    if len(modes2) !=1:
        m01 =  (len(seq1) - modes1[0][0]) + (len(seq2) - modes2[1][0])
    if len(modes1) !=1:
        m10 =  (len(seq1) - modes1[1][0]) + (len(seq2) - modes2[0][0])
    min_change = min(m01,m10)
    
print(min_change)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

memo = [[[[-1 for l in range(2)] for k in range(2)] for j in range(D)] for i in range(N)]

def f(digit, current_sum, flagX, flagY): #flagX upper bound, flagY lower bound
    if digit == -1:
        if flagY and current_sum % D == 0:
            return 1
        else:
            return 0

    if memo[digit][current_sum][flagX][flagY] != -1:
        return memo[digit][current_sum][flagX][flagY]

    ret = 0
    for i in range(10):
        if flagX:
            ret += f(digit-1, (current_sum+i)%D, flagX, flagY or (1 if i >= 1 else 0))
        elif i == int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 0, flagY or (1 if i >= 1 else 0))
        elif i < int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 1, flagY or (1 if i >= 1 else 0))
            
    memo[digit][current_sum][flagX][flagY] = ret % MOD
    return ret

print(f(N-1, 0, 0, 0) % MOD)


### FIXED CODE ###

K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

dp = [[[0 for k in range(2)] for j in range(D)] for i in range(N+1)]

dp[0][0][0] = 1
for i, n in enumerate(K):
    n = int(n)
    for j in range(D):
        for k in range(2):
            for d in range(10 if k else n+1):
                dp[i+1][(j+d) % D][k or d < n] += dp[i][j][k]
                dp[i+1][(j+d) % D][k or d < n] %= MOD

print((dp[N][0][0] + dp[N][0][1] - 1) % MOD)
### BUGGY CODE ###

Q = int(input())
l = [0 for q in range(Q)]
r = [0 for q in range(Q)]
for q in range(Q):
  l[q], r[q] = map(int, input().split(' '))
max_r = max(r)
prime_numbers = [True for n in range(max_r+1)]
similar_numbers = [False for n in range(max_r+1)]

prime_numbers[0], prime_numbers[1] = False, False    # 1 is not a prime number
for divisor in range(2, max_r//2 + 1):
  if prime_numbers[divisor]:
    for multipler in range(2, max_r//divisor + 1):
      prime_numbers[divisor * multipler] = False
      
for N in range(1, max_r + 1, 2):
  if prime_numbers[N] and prime_numbers[(N+1)//2]:
    similar_numbers[N] = True
    
for q in range(Q):
  print(sum(similar_numbers[l[q]:r[q]+1]))

### FIXED CODE ###

import itertools

Q = int(input())
l = [0 for q in range(Q)]
r = [0 for q in range(Q)]
for q in range(Q):
  l[q], r[q] = map(int, input().split(' '))
max_r = max(r)
prime_numbers = [True for n in range(max_r+1)]
similar_numbers = [False for n in range(max_r+1)]
 
prime_numbers[0], prime_numbers[1] = False, False    # 1 is not a prime number
for divisor in range(2, max_r//2 + 1):
  if prime_numbers[divisor]:
    for multipler in range(2, max_r//divisor + 1):
      prime_numbers[divisor * multipler] = False
      
for N in range(1, max_r + 1, 2):
  if prime_numbers[N] and prime_numbers[(N+1)//2]:
    similar_numbers[N] = True
accumulate_sim_nums = list(itertools.accumulate(map(int, similar_numbers)))
    
for q in range(Q):
  print(accumulate_sim_nums[r[q]]-accumulate_sim_nums[l[q]-1])
### BUGGY CODE ###

N = int(input())
z = [tuple(map(int,input().split())) for i in range(N)]
z.sort()
y = [(z[i][1],i) for i in range(N)]
y.sort()
cost = [[] for i in range(N)]
for i in range(N):
    j = y[i][1]
    if i != 0:
        cost[i].append((i-1,z[i][0]-z[i-1][0]))
        cost[i].append((i-1,abs(z[i][1]-z[i-1][1])))
        j_ = y[i-1][1]
        cost[j].append((j_,y[i][0]-y[i-1][0]))
        cost[j].append((j_,abs(z[j][0]-z[j_][0])))
    if i != N-1:
        cost[i].append((i+1,z[i+1][0]-z[i][0]))
        cost[i].append((i+1,abs(z[i+1][1]-z[i][1])))
        j_ = y[i+1][1]
        cost[j].append((j_,y[i+1][0]-y[i][0]))
        cost[j].append((j_,abs(z[j_][1]-z[j][1])))

import heapq

def prim(cost):
    V = len(cost)
    res = 0
    mincost = [float('inf')]*V
    used = [False]*V
    hq = []
    mincost[0] = 0
    heapq.heappush(hq,(0,0))
    while hq:
        weight,u = heapq.heappop(hq)
        if used[u]:
            continue
        used[u] = True
        res += weight
        mincost[u] = weight
        for v, v_cost in cost[u]:
            if not used[v]:
                heapq.heappush(hq,(v_cost,v))
    return res

print(prim(cost))

### FIXED CODE ###

N = int(input())
z = [tuple(map(int,input().split())) for i in range(N)]
z.sort()
y = [(z[i][1],i) for i in range(N)]
y.sort()
cost = [[] for i in range(N)]
for i in range(N-1):
    j = y[i][1]
    cost[i].append((i-1,min(abs(z[i][0]-z[i-1][0]),abs(z[i][1]-z[i-1][1]))))
    j_ = y[i-1][1]
    cost[j].append((j_,min(abs(y[i][0]-y[i-1][0]),abs(z[j][0]-z[j_][0]))))
    cost[i].append((i+1,min(abs(z[i+1][0]-z[i][0]),abs(z[i+1][1]-z[i][1]))))
    j_ = y[i+1][1]
    cost[j].append((j_,min(abs(y[i+1][0]-y[i][0]),abs(z[j_][1]-z[j][1]))))

i = N-1
j = y[i][1]
cost[i].append((i-1,min(abs(z[i][0]-z[i-1][0]),abs(z[i][1]-z[i-1][1]))))
j_ = y[i-1][1]
cost[j].append((j_,min(abs(y[i][0]-y[i-1][0]),abs(z[j][0]-z[j_][0]))))


import heapq

def prim(cost):
    V = len(cost)
    res = 0
    mincost = [float('inf')]*V
    used = [False]*V
    hq = []
    mincost[0] = 0
    heapq.heappush(hq,(0,0))
    done = 0
    while hq:
        weight,u = heapq.heappop(hq)
        if not used[u]:
            used[u] = True
            done += 1
            res += weight
            mincost[u] = weight
            for v, v_cost in cost[u]:
                if not used[v]:
                    heapq.heappush(hq,(v_cost,v))
            if done == V:
                break
    return res

print(prim(cost))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
mod = 10**9+7

nCr = {}
def mod_cmb(n, r):
    if r == 0 or r == n:
        return 1
    if r == 1:
        return n
    if (n,r) in nCr:
        return nCr[(n,r)]
    nCr[(n,r)] = (mod_cmb(n-1,r) + mod_cmb(n-1,r-1))%mod
    return nCr[(n,r)]


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

ans = 0
for i in range(N-K+1):
    ans += A[-1-i]*mod_cmb(N-1-i, K-1)
    ans %= mod
    ans -= A[i]*mod_cmb(N-1-i, K-1)
    ans %= mod

print(ans)

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

ans = 0
for i in range(N-K+1):
    ans += A[-1-i]*cmb(N-1-i, K-1, mod)
    ans %= mod
    ans -= A[i]*cmb(N-1-i, K-1, mod)
    ans %= mod

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

import fractions
from functools import reduce
import itertools


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

ans = []

for a in list(itertools.combinations(A, N-1)):
    ans.append(reduce(fractions.gcd, a))
print(max(ans))


### FIXED CODE ###

import fractions


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

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

ans = []
for i in range(N):
    ans.append(fractions.gcd(gcd_l[i], gcd_r[i+1]))

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

k, s = map(int, input().split())

count = 0

for a in range(k+1):
  for b in range(k+1):
    for c in range(k+1):
      if a+b+c == s:
        count += 1

print(count)

### FIXED CODE ###

k, s = map(int, input().split())

count = 0

for i in range(k+1):
  a = i
  for j in range(k+1):
    b = j
    if a+b>s:
      break
    if s-(a+b)<=k:
      count+=1

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

N,M = map(int,input().split())
edge_from = [[] for _ in range(N+1)]
edge_to = [[] for _ in range(N+1)]
ans = [-1]*(N+1)
arr = []
child = set()
parent = -1
for _  in range(N-1+M):
    go,to = map(int,input().split())
    edge_from[go].append(to)
    edge_to[to].append(go)
    arr.append((go,to))
    child.add(to)
for i in range(1,N+1):
    if i not in child:
        parent = i
stack = [parent]
distance = [-1]*(N+1)
distance[parent] = 0
while stack:
    v = stack.pop()
    for u in edge_from[v]:
        distance[u] = max(distance[v] + 1,distance[u])
        stack.append(u)
for i in range(1,N+1):
    if i == parent :
        ans[i] = 0
    else:
        for j in edge_to[i]:
            if distance[j] == distance[i] -1:
                ans[i] = j
                break
for i in range(1,N+1):
    print(ans[i])           

### FIXED CODE ###

from collections import defaultdict, deque
import heapq
v, n = map(int, input().split())
es = [[int(x) for x in input().split()] for _ in range(v+n-1)]

outs = defaultdict(list)
ins = defaultdict(int)
edge_from = [[] for _ in range(v+1)]
edge_to = [[] for _ in range(v+1)]
ans = [-1]*(v+1)
for v1, v2 in es:
    edge_from[v1].append(v2)
    edge_to[v2].append(v1)
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
rev = [0]*(v+1)
for i in range(1,v+1):
    rev[res[i]] = i
redge_to = [[] for _ in range(v+1)]
for i in range(1,v+1):
    for j in edge_to[i]:
        ri = rev[i]
        rj = rev[j]
        heapq.heappush(redge_to[ri],-rj)
for ri in range(1,v+1):
    if redge_to[ri]:
        rj = redge_to[ri][0]
        i = res[ri]
        j = res[-rj]
        ans[i] = j
    else:
        i =res[ri]
        ans[i] = 0
for i in ans[1:]:
    print(i)
### BUGGY CODE ###

import bisect

N=[int(x)for x in input().split()]
D=[int(x) for x in input().split()]

D.sort()
total=0

for i in range(len(D)-2):
    for j in range(i+1,len(D)-1):
        total+= bisect.bisect_left(D[j+1:],D[i]+D[j])

print(total)

### FIXED CODE ###

import bisect

N=int(input())
D=[int(x) for x in input().split()]

D.sort()
total=0

for i in range(N-2):
    for j in range(i+1,N-1):
        total+=bisect.bisect_left(D,D[i]+D[j])-j-1

print(total)
### BUGGY CODE ###

from collections import defaultdict
n, p = map(int, input().split())
s = input()
s = list(map(int, s))

# dp[i][j] = (s[i]で終わる部分文字列で、pで割ったあまりがjな数の個数)
dp = [defaultdict(int), defaultdict(int)]

ans = 0
for i in range(n):
    i0, i1 = (i + 0) % 2, (i + 1) % 2

    dp[i1] = defaultdict(int)
    for j in dp[i0]:
        dp[i1][(j * 10 + s[i]) % p] += dp[i0][j]
    dp[i1][s[i] % p] += 1

    ans += dp[i1][0]
    # print(dp[i1])

print(ans)


### FIXED CODE ###

from collections import defaultdict


def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    ans = 1
    for i in range(1, k + 1):
        ans *= n - i + 1
        ans //= i
    return ans


n, p = map(int, input().split())
s = input()

if p == 2:
    ans = 0
    for i in range(n):
        if int(s[i]) % 2 == 0:
            ans += i + 1
elif p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) in [0, 5]:
            ans += i + 1
else:
    mod_list = [0] * (n + 1)
    d = 1
    for i in reversed(range(n)):
        mod_list[i] = int(s[i]) * d + mod_list[i + 1]
        mod_list[i] %= p
        d = (d * 10) % p

    mod_dict = defaultdict(int)
    for i in range(n + 1):
        mod_dict[mod_list[i]] += 1

    # print(mod_list)
    # print(mod_dict)

    ans = 0
    for c in mod_dict:
        ans += comb(mod_dict[c], 2)

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

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

H = sorted(H, reverse=True)

for i in range(K):
    if(len(H) == 0):
        print(0)
        end = 0
        break
    H.pop(0)

if(len(H) > 0):
    print(sum(H))

### FIXED CODE ###

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

H = sorted(H, reverse=True)

if K > N:
    print(0)
else:
    print(sum(H[K:]))
### BUGGY CODE ###

import sys
n,m=map(int,input().split())
l=[[int(i) for i in l.split()] for l in sys.stdin]
s=[[0] for i in range(10**5+1)]
for i in l:
  s[i[0]].append(i[1])
for i in range(len(s)):
  s[i].sort()
for i in l:
  print('{:0>6}{:0>6}'.format(str(i[0]),str(s[i[0]].index(i[1]))))

### FIXED CODE ###

import sys
import bisect
n,m=map(int,input().split())
l=[[int(i) for i in l.split()] for l in sys.stdin]
s=[[0] for i in range(10**5+1)]
for i in l:
  s[i[0]].append(i[1])
for i in range(len(s)):
  s[i].sort()
for i in l:
  print('{:06}{:06}'.format(i[0],bisect.bisect_left(s[i[0]],i[1])))
### BUGGY CODE ###

s = input()
len = len(s)
count = 0
for i in range(len):
    for j in range(i, len):
        str = s[i:j+1]
        if int(str) % 2019 == 0:
            count += 1
print(count)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N=int(input())
S=list(map(int,input().split()))

ans=10**10

ave=0
for i in range(N):
    ave+=S[i]
ave=ave//N

for i in range(ave-200000,ave+10000):
    goukei=0
    for j in range(N):
        goukei+=abs(S[j]-(i+j+1))
        
    if ans>goukei:
        ans=goukei
        
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import statistics

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

S1=[]
for i in range(N):
    S1.append(S[i]-i)
S1.sort()
chuouchi=statistics.median_high(S1)
chuouchi2=statistics.median_low(S1)
chuouchi3=statistics.median(S1)
ans=10**20
ansj=0
A=chuouchi-4
B=chuouchi+4
C=chuouchi2-4
D=chuouchi2+4
E=int(chuouchi3)-4
F=int(chuouchi3)+4
for i in range(A,B):
    goukei=0
    for j in range(N):
        goukei+=abs(S[j]-(i+j+1))
        
    if ans>goukei:
        ans=goukei
        
for i in range(C,D):
    goukei=0
    for j in range(N):
        goukei+=abs(S[j]-(i+j+1))
        
    if ans>goukei:
        ans=goukei

for i in range(E,F):
    goukei=0
    for j in range(N):
        goukei+=abs(S[j]-(i+j+1))
        
    if ans>goukei:
        ans=goukei        
        
print(ans)
### BUGGY CODE ###

from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    table = [True] * (10**6 + 1)
    for _a in a:
        if table[_a]:
            for i in range(2 * _a, max(a) + 1, _a):
                table[i] = False
    return str(sum(table[k] for k, v in Counter(a).items() if v == 1))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


### FIXED CODE ###

import numpy as np
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    table = np.array([True] * (10**6 + 1))
    for _a in a:
        if table[_a]:
            table[2*_a::_a]=False
    i = np.array([k for k,v in Counter(a).items() if v==1],dtype=np.int)
    return str(table[i].sum())


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
### BUGGY CODE ###


def asum(l,r):
	global cumsum
	l+=1
	r+=1
	return cumsum[r-1]-cumsum[l-1]
def check(l,r):
	global dp
	if l==r:
		return 0
	if l == r-1:
		return arr[l]+arr[r]
	if dp[l][r] != None:
		return dp[l][r]
	else:
		ans = 10**18
		for i in range(l, r):
			st1 = asum(l,i)
			st2 = asum(i,r+1)
			ans = min(st1 + st2 + check(l,i)+ check(i+1, r), ans)
		
		dp[l][r] = ans
		return ans





ll = int(input())
arr = [int(i) for i in input().split()]
cumsum = [0]

for i in arr:
	cumsum.append(cumsum[-1]+i)
dp = [[None for i in range(ll+1)] for j in range(ll+1)]
print(check(0, ll-1))


### FIXED CODE ###


def asum(l,r):
	global cumsum
	l+=1
	r+=1
	return cumsum[r-1]-cumsum[l-1]
def check(l,r):
	global dp
	if l==r:
		return 0
	if l == r-1:
		return arr[l]+arr[r]
	if dp[l][r] != None:
		return dp[l][r]
	else:
		ans = 10**18
		for i in range(l, r):
			st1 = asum(l,i)
			st2 = asum(i,r+1)
			ans = min(st1 + st2 + check(l,i)+ check(i+1, r), ans)
		
		dp[l][r] = ans
		return ans





ll = int(input())
arr = [int(i) for i in input().split()]
cumsum = [0]

for i in arr:
	cumsum.append(cumsum[-1]+i)
dp = [[None for i in range(ll+1)] for j in range(ll+1)]
print(check(0, ll-1))