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

N = int(input())
AA = list(map(int,input().split()))
AAwIdx = [[0]*2 for _ in range(N)]
for i in range(N):
    AAwIdx[i][0] = i
    AAwIdx[i][1] = AA[i]
AA_sorted = sorted(AAwIdx, key=lambda x: x[1], reverse=True)
#print(AA_sorted)

answer = [[0]*(N+1) for _ in range(N+1)]

ans_all = 0
Idx_i = 0
Idx_f = N-1
for i in range(0,N):
    for no in range(i+1):
        idxi = i-no
        idxf = Idx_f-no
        answer[i+1-no][no] = max(answer[i+1-no][no],answer[i-no][no] + abs(AA_sorted[i][0]-idxi)*AA_sorted[i][1])
        answer[i-no][no+1] = max(answer[i-no][no+1],answer[i-no][no] + abs(AA_sorted[i][0]-idxf)*AA_sorted[i][1])
        #print('idx:',AA_sorted[i][0], 'val:',AA_sorted[i][1],'idx_i:',idxi, 'idx_f:',idxf)
        #print('idx:',i-no,no,'ans:',answer[i-no][no])
        #print('idx:',i+1-no,no,'ans:',abs(AA_sorted[i][0]-idxi)*AA_sorted[i][1])
        #print('idx:',i-no,no+1,'ans:',abs(AA_sorted[i][0]-idxf)*AA_sorted[i][1])
        ans_all = max(answer[i+1-no][no], ans_all)
        ans_all = max(answer[i-no][no+1], ans_all)
#print(np.array(answer))
#    print(AAs)
#print(AnsIdx)
print(ans_all)

### FIXED CODE ###

def solve():
    INF = float('inf')
 
    def max2(x, y): return x if x >= y else y
 
    N = int(input())
    As = [(A, i) for i, A in enumerate(map(int, input().split()))]
 
    As.sort(reverse=True)
 
    dp = [[-INF]*(N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for no, (A, pos) in enumerate(As):
        for i in range(no+1):
            j = no-i
            dp[i+1][j] = max2(dp[i+1][j], dp[i][j] + A*abs(pos-i))
            dp[i][j+1] = max2(dp[i][j+1], dp[i][j] + A*abs(pos-(N-1-j)))
 
    ans = 0
    for i in range(N+1):
        j = N-i
        ans = max2(ans, dp[i][j])
 
    print(ans)
 
 
solve()
### BUGGY CODE ###

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

for i in range(m):
    b, c = map(int, input().split())
    if min(test) < c:
        test_1 = [c if test[j]<c else test[j] for j in range(b)]
        test = test_1 + test[b:]
        test.sort()
print(sum(test))

### FIXED CODE ###

from collections import defaultdict

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

test_dict = defaultdict(int)

for j in test:
    test_dict[j] += 1

for k in range(m):
    b, c = map(int, input().split())
    test_dict[c] += b

count = 0
sum_val = 0
for l in sorted(test_dict, reverse=True):
    if n-count>0:
       sum_val += l * min(test_dict[l], n-count)
       count += min(test_dict[l], n-count)
    else:
       break
print(sum_val)
### BUGGY CODE ###

import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    w = [0] * (10 ** 6 + 1)
    for a in A:
        w[a] += 1
    for a in A:
        for b in range(a * 2, 10 ** 6 + 1, a):
            w[b] = 0
        if w[a] >= 2:
            w[a] = 0
    print(sum(w))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    w = [0] * (10 ** 6 + 1)
    for a in A:
        w[a] += 1
    f = [False] * (10 ** 6 + 1)
    for a in A:
        if f[a]:
            w[a] = 0
            continue
        for b in range(a * 2, 10 ** 6 + 1, a):
            w[b] = 0
        f[a] = True
    print(sum(w))

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

s = list(input())

i = 0
imax = len(s) - 2
count = 0
while i < imax:
	if s[i] == "A" and s[i + 1] == "B" and s[i + 2] == "C":
		s[i] = "B"
		s[i + 1] = "C"
		s[i + 2] = "A"
		count += 1
		if i > 0:
			i -= 1
	else:
		i += 1

print(count)


### FIXED CODE ###

A = 0
B = 1
C = 2

table = {"A": A, "B": B, "C": C}

s = [table[c] for c in input()]
s.reverse()

total = 0
bc_count = 0
prev = None
for c in s:
	if c == A:
		if prev == C:
			bc_count = 0
		else:
			total += bc_count
	elif c == B:
		if prev == C:
			bc_count += 1
		else:
			bc_count = 0
	elif c == C:
		if prev == C:
			bc_count = 0
	prev = c

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

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
BC = sorted(
    [list(map(int, input().split())) for _ in range(M)],
    reverse=True,
    key=lambda x: x[1]
)
 
BClist = []
for m in range(M):
    b, c = BC[m]
    BClist.extend([c for _ in range(b)])
    if len(BClist) > N:
        break
 
final_list = []
for n in range(N):
    if BClist == []:
        new = A[0]
        A.pop(0)
    else:
        if A[0] > BClist[0]:
            new = A[0]
            A.pop(0)
        else:
            new = BClist[0]
            BClist.pop(0)
    final_list.append(new)
print(sum(final_list))

### FIXED CODE ###

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
BC = sorted(
    [list(map(int, input().split())) for _ in range(M)],
    reverse=True,
    key=lambda x: x[1]
)

BClist = []
for m in range(M):
    b, c = BC[m]
    BClist.extend([c for _ in range(b)])
    if len(BClist) > N:
        break

final_list = [None]*N
i_a = 0
i_bc = 0
for n in range(N):
    if i_bc >= len(BClist):
        final_list[n] = A[i_a]
        i_a += 1
    else:
        if A[i_a] > BClist[i_bc]:
            final_list[n] = A[i_a]
            i_a += 1
        else:
            final_list[n] = BClist[i_bc]
            i_bc += 1
print(sum(final_list))
### BUGGY CODE ###

N=int(input())
S=input()
R=0

def judge(i,j,k):
  if j-i == k-j:
    return False
  else:
    if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
      # print(i,j,k, "True")
      return True
  # print(i,j,k, "False")
    else:
      return False

for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if judge(i,j,k):
        R+=1

print(R)

### FIXED CODE ###

n = int(input())
s = input()
result = 0

r = s.count('R')
g = s.count('G')
b = s.count('B')

result = r * g * b
count = 0

for i in range(n):
    for j in range(i, n):
        k = 2 * j - i
        if j < k < n:
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                count += 1

print(result-count)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
def LI():return list(map(int,input().split()))
def yes():print("YES")
def no():print("NO")

n,k=LI()
a=LI()

if k>=n:
    ans=[n]*n
    print(*ans)
    exit()


for _ in range(k):
    b=[0]*n
    for i in range(n):
        q=a[i]
        for j in range(i-q,i+q+1):
            if 0<=j<=n-1:
                b[j]+=1
    a=b[:]
    # print(_,a)
print(*a)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import time
t1=time.time()
def LI():return list(map(int,input().split()))
n,k=LI()
a=LI()

for _ in range(k):
    tab=[0]*(n)
    for i in range(n):
        q=a[i]
        if 0<=i-q:
            tab[i-q]+=1
        else:
            tab[0]+=1
        if i+q+1<=n-1:
            tab[i+q+1]-=1
        else:
            pass
    b=[tab[0]]
    for i in range(n-1):
        b.append(tab[i+1]+b[-1])
    a=b[:]
    if time.time()-t1>1.5:
        print(*a)
        exit()
print(*a)
### BUGGY CODE ###

import math
import itertools
import functools
import numpy as np
import operator



# a, b = map(float, input().split())

# b = int(b * 100)
# a = int(a)

# print(int(a * b / 100))

n = int(input())
v = [int(i) for i in input().split()]
ans = functools.reduce(operator.mul, v)
 
if ans > 1e18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import math
import itertools
import functools
import numpy as np



# a, b = map(float, input().split())

# b = int(b * 100)
# a = int(a)

# print(int(a * b / 100))

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

if v[0] == 0:
  print(0)
  exit(0)
ans = 1
for l in v:
    ans *= l
    if ans > 1e18:
      print(-1)
      exit(0)
 
if ans > 1e18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n, a, b = map(int, input().split())
    
l = ""
flag = True
count = 0
while True:
    if flag == True:
        for x in range(a):
            l += "b"
        flag = False
    else:
        for y in range(b):
            l += "r"
        flag = True

    if len(l) >= n:
        break
    
for c in range(n):
    if l[c] == "b":
        count += 1

print(count)


### FIXED CODE ###

N, A, B = map(int, input().split())
ans = N // (A + B) * A
rem = N % (A + B)
ans += min(rem, A)
print(ans)
### BUGGY CODE ###

from collections import Counter


def check(s1, s2, i, j, memo):
    if memo[i] == memo[j] and memo[i] != -1:
        return 1
    elif memo[i] != memo[j] and memo[j] != -1:
        return 0

    if s1 == s2:
        if memo[i] == -1:
            memo[i] = i
            memo[j] = i
        elif memo[j] == -1:
            memo[j] = memo[i]
        return 1

    else:
        return 0


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

    S = []
    for _ in range(N):
        s = input()
        S.append(Counter(s))

    ans = 0
    memo = [-1 for i in range(N)]
    for i in range(N):
        for j in range(i+1, N):
            ans += check(S[i], S[j], i, j, memo)

    print(ans)


main()

### FIXED CODE ###

import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
ans_dict = {}

for _ in range(n):
    s = list(input())
    s.sort()
    s = ''.join(s)
    try:
        ans_dict[s] += 1
    except:
        ans_dict[s] = 1

ans = 0
for key in ans_dict:
    if ans_dict[key] >= 2:
        ans += combinations_count(ans_dict[key], 2)
print(ans)
### BUGGY CODE ###

import itertools
import sys

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))

ids = [x for x in range(n)]
# print(ids)
# sys.exit()
cmb = list()
for i in range(1, n+1):
    cmb += list(itertools.combinations(ids, i))
# print(cmb)

store = [0]*len(cmb)
store.append(0)

for k, i in enumerate(cmb):
    tmpv = 0
    tmpc = 0
    for j in i:
        tmpv += v[j]
        tmpc += c[j]
    store[k] = tmpv - tmpc

# print(store)
result = max(store)
print(result)


### FIXED CODE ###

import itertools
import sys

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))

ids = [x for x in range(n)]

diff = [tmpv - tmpc for tmpv, tmpc in zip(v, c)]

result = 0

for i in range(1, n+1):
    tmp = list(itertools.combinations(diff, i))
    tmpMax = max([sum(x) for x in tmp])
    if tmpMax > result:
        result = tmpMax
    # store.extend([sum(x) for x in tmp])
    # print(store)
    # for x, y in zip(vset, cset):
    #     store.append(sum(x)-sum(y))

print(result)
### BUGGY CODE ###

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

dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 1
for j in range(M + 1):
    dp[0][j] = 1

for i, a in enumerate(A, start=1):
    for j, b in enumerate(B, start=1):
        if a == b:
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD
        else:
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % MOD

print(dp[N][M])


### FIXED CODE ###

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

dp = [[0] * (M + 1) for _ in range(N + 1)]  # dp[s][t]

for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        v = dp[i - 1][j] + dp[i][j - 1]
        if s == t:
            v += 1
        else:
            v -= dp[i - 1][j - 1]
        dp[i][j] = v % MOD

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

import bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
cnt = 0
for i in range(n-1, 1, -1):
    for j in range(i-1, 0, -1):
        plus = l[i]+l[j]
        minus = l[i]-l[j]
        bir = min(j, bisect.bisect(l, plus))
        bil = bisect.bisect(l, minus)
        if bir > bil:
            cnt += bir-bil
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
cnt = 0
for i in range(n-1, 1, -1):
    for j in range(i-1, 0, -1):
        plus = l[i]+l[j]
        minus = l[i]-l[j]
        bir = min(j, bisect.bisect(l, plus))
        bil = bisect.bisect(l, minus)
        if bir > bil:
            cnt += bir-bil
print(cnt)
### BUGGY CODE ###

import numpy as np
N = int(input())
A_list = sorted(list(map(int, input().split())), reverse=True)

edge_list = [A_list[0]]
score = 0
for i, a in enumerate(A_list[1:]):
    maxidx = np.argmax(edge_list)
    if edge_list[maxidx] == 1:
        break
    score += edge_list[maxidx]
    #print(edge_list, maxidx, score)
    edge_list[maxidx] = a
    edge_list.insert(maxidx, a)
    #print(edge_list)
else:
    print(score)
    exit()
score += N - i - 1
print(score)


### FIXED CODE ###

import queue

N = int(input())
A_list = sorted(list(map(int, input().split())), reverse=True)

edge_que = queue.Queue()
edge_que.put(A_list[0])
score = 0
for i, a in enumerate(A_list[1:]):
    score += edge_que.get()
    edge_que.put(a)
    edge_que.put(a)
print(score)
### BUGGY CODE ###

from fractions import gcd
A,B=map(int,input().split())
C=gcd(A,B)
kouyakusuu=[]

for i in range(1,C+1):
   if C%i==0:
      kouyakusuu.append(i)

from collections import deque
import math

def eratosthenes(limit):
   A=[c for c in range(3,limit+1,2)]
   A.insert(0,2)
   P=deque()

   while True:
      prime_number=A[0]

      if prime_number > math.sqrt(limit):
         break

      P.append(prime_number)

      i=0
      while i < len(A):
         if A[i] % prime_number == 0:
            A.pop(i)
            continue
         i += 1

   for a in A:
      P.append(a)

   li=list(P)
   return(li)

prime_numbers=eratosthenes(C)
print(len(set(kouyakusuu)&set(prime_numbers))+1)

### FIXED CODE ###

from fractions import gcd
A,B=map(int,input().split())
C=gcd(A,B)

if C==1:
   print(1)
else:
   count=1
   C_copy=C
   n=2
   while n**2<=C:
      flag=False
      while C_copy%n==0:
         C_copy//=n
         flag=True
      if flag:
         count+=1
         n=n+1 if n==2 else n+2
      else:
         n=n+1 if n==2 else n+2
   
   if C_copy!=1:
      count+=1

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

n, m = map(int, input().split())
g = [[] for _ in range(n)]
inv = [0] * n
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    inv[b - 1] += 1
for i in range(n):
    if inv[i] == 0:
        root = i
        break
d = [0] * n
s = [root]
while s:
    p = s.pop()
    for node in g[p]:
        d[node] = max(d[node], d[p] + 1)
        s.append(node)
ans = [0] * n
for i in range(n):
    for node in g[i]:
        if d[node] == d[i] + 1:
            ans[node] = i + 1
for x in ans:
    print(x)


### FIXED CODE ###

n, m = map(int, input().split())
g = [[] for _ in range(n)]
inv = [0] * n
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    inv[b - 1] += 1
for i in range(n):
    if inv[i] == 0:
        root = i
        break
d = [0] * n
s = [root]
while s:
    p = s.pop()
    for node in g[p]:
        inv[node] -= 1
        if inv[node] == 0:
            d[node] = max(d[node], d[p] + 1)
            s.append(node)
ans = [0] * n
for i in range(n):
    for node in g[i]:
        if d[node] == d[i] + 1:
            ans[node] = i + 1
for x in ans:
    print(x)
### BUGGY CODE ###

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

list=[]
for _ in range(n):
  a,b=(map(int,input().split()))
  list+=[a]*b
  
print(sorted(list)[k-1])

### FIXED CODE ###

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

ans_list=[0]*(10**5+1)
#print(len(ans_list))

for _ in range(n):
  a,b=(map(int,input().split()))
  ans_list[a]+=b

#print(ans_list)
s=0
ans=0

for n,i in enumerate(ans_list):
  s+=i
  ans=n
  if s>=k:
    print(ans)
    break
### BUGGY CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,a,b = map(int,ipt().split())
    if a*b < n or a+b-1 > n:
        print(-1)
        exit()
    ans = [[b-i] for i in range(b)]
    si = n-a+2
    ue = n+1
    i = 0
    while True:
        if si <= b:
            break
        for j in range(si,ue):
            ans[i].append(j)
        ue = si
        si -= a-1
        i += 1
    for j in range(b+1,ue):
        ans[i].append(j)
    aa = [" ".join(map(str,i)) for i in ans]
    print(" ".join(aa))
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,a,b = map(int,ipt().split())
    if a*b < n or a+b-1 > n:
        print(-1)
        exit()
    ans = [str(b-i) for i in range(b)]
    si = n-a+2
    ue = n+1
    i = 0
    while True:
        if si <= b or a == 1:
            break
        ans[i] += " "+" ".join(map(str,range(si,ue)))
        ue = si
        si -= a-1
        i += 1
    if i < b and b+1 < ue:
        ans[i] += " "+" ".join(map(str,range(b+1,ue)))
    print(" ".join(ans))
    return

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

l, r = map(int, input().split())
mod1 = []
mod2 = []
for i in range(l,r+1):
  mod1.append(i%2019)
#print(mod1)
if min(mod1)==0:
  print(0)
else:
  for i in range(len(mod1)-1):
    for j in range(i+1,len(mod1)):
      mod2.append((mod1[i]*mod1[j])%2019)
	#print(mod2)
  print(min(mod2))


### FIXED CODE ###

l, r = map(int, input().split())
mod1 = []
mod2 = []
cccc=0
for i in range(l,r+1):
  b=i%2019
  mod1.append(b)
  if b==0:
    cccc=1
    break
#print(mod1)
if cccc==1:
  print(0)
else:
  for i in range(len(mod1)-1):
    for j in range(i+1,len(mod1)):
      mod2.append((mod1[i]*mod1[j])%2019)
	#print(mod2)
  print(min(mod2))
### BUGGY CODE ###

a, b = map(int, input().split())
def cf(x1,x2):
  cf=[]
  for i in range(2,min(x1,x2)+1):
    if x1 % i == 0 and x2 % i == 0:
      cf.append(i)
  return cf

Oks = []
for cand in cf(a,b):
  for div in Oks:
    if cand % div == 0:
      break
  else:
    Oks.append(cand)
print(len(Oks) + 1)

### FIXED CODE ###

a, b = map(int, input().split())
from collections import defaultdict

def comdiv(n):
  end = int(n**0.5) + 2
  dic = defaultdict(lambda: 0)
  for i in range(2, end):
    while n % i == 0:
      n //= i
      dic[i] += 1
  else:
    if n > 1:
      dic[n] = 1
  return dic

A = comdiv(a).keys()
B = comdiv(b).keys()
C = set(A) & set(B)
print(len(C) + 1)
### BUGGY CODE ###

class RollingHash:
    def __init__(self,S,base,M):
        self.N=len(S)
        self.M=M
        self.H=[0]*(self.N+1)
        self.B=[0]*(self.N+1)
        self.B[0]=1
        for i in range(self.N):
            self.B[i+1]=self.B[i]*base%M
            self.H[i+1]=(self.H[i]*base+(ord(S[i])-96))%M
    def get(self,l,r):
        return (self.H[r]-self.H[l]*self.B[r-l]+self.M)%self.M
    def getall(self,L):
        arr=[]
        for i in range(L,self.N+1):
            arr.append(self.get(i-L,i))
        return arr

def Hash(S,base,M):
    H=0
    for c in S:
        H=(H*base+ord(c)-96)%M
    return H
    
import random

N=int(input())
M=2**61-1
base=random.randrange(100,M)
RH,S=[None for i in range(N)],[None]*N
for i in range(N):
    s=input()
    S[i]=s
    RH[i]=RollingHash(s,base,M)

dic={}
dic[0]={}
for k,s in enumerate(S):
    Set=set()
    l=len(s)
    for j in range(l):
        Hash=RH[k].get(j,l)
        if not Hash in dic:
            dic[Hash]={}
        for c in Set:
            if not c in dic[Hash]:
                dic[Hash][c]=1
            else:
                dic[Hash][c]+=1
        Set.add(s[j])
    for c in Set:
        if not c in dic[0]:
            dic[0][c]=1
        else:
            dic[0][c]+=1
ans=0
for i,s in enumerate(S):
    Hash=RH[i].get(1,len(s))
    ans+=dic[Hash][s[0]]-1
print(ans)

### FIXED CODE ###

class RollingHash:
    def __init__(self,S,base,M):
        self.N=len(S)
        self.M=M
        self.H=[0]*(self.N+1)
        self.B=[0]*(self.N+1)
        self.B[0]=1
        for i in range(self.N):
            self.B[i+1]=self.B[i]*base%M
            self.H[i+1]=(self.H[i]*base+(ord(S[i])-96))%M
    def get(self,l,r):
        return (self.H[r]-self.H[l]*self.B[r-l]+self.M)%self.M

def main():
    import random

    N=int(input())
    M=2**61-1
    base=random.randrange(100,M)
    RH,S=[],[]
    RH,S=[None for i in range(N)],[None]*N
    for i in range(N):
        s=input()
        S[i]=s
        RH[i]=RollingHash(s,base,M)

    dic={}
    dic[0]=[0]*26
    for k,s in enumerate(S):
        Set=set()
        l=len(s)
        for j in range(l):
            Hash=RH[k].get(j,l)
            if not Hash in dic:
                dic[Hash]=[0]*26
            for c in Set:
                dic[Hash][ord(c)-97]+=1
            Set.add(s[j])
        for c in Set:
            dic[0][ord(c)-97]+=1
    ans=0
    for i,s in enumerate(S):
        Hash=RH[i].get(1,len(s))
        ans+=dic[Hash][ord(s[0])-97]-1
    print(ans)

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

import sys
sys.setrecursionlimit(10**5)

h,n=map(int,input().split())
magic=[]
for i in range(n):
  magic.append(tuple(map(int,input().split())))

memo={}
def d(hp):
  if hp<=0:
    return 0
  if hp in memo:
    return memo[hp]
  mn=10**10
  for i in magic:
    mn=min(mn,d(hp-i[0])+i[1])
  memo[hp]=mn
  return mn

print(d(h))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

h,n=map(int,input().split())
magic=[]
for i in range(n):
  magic.append(tuple(map(int,input().split())))

memo={}
def d(hp):
  if hp<=0:
    return 0
  if hp in memo:
    return memo[hp]
  mn=10**10
  for i in magic:
    mn=min(mn,d(hp-i[0])+i[1])
  memo[hp]=mn
  return mn

for i in range(1,h-1):
  d(i)
print(d(h))
### BUGGY CODE ###

if __name__ == '__main__':
    MOD = 2019

    S = [int(s) for s in input()]
    N = len(S)
    dp = [[float('inf') for _ in range(N + 1)] for _ in range(N + 1)]

    dp[0][0] = S[0] % MOD

    for i in range(N):
        for j in range(i, N):
            if i == j:
                dp[i][j] = S[i] % MOD
            else:
                dp[i][j] = (dp[i][j - 1] * 10 + S[j]) % MOD

    print(sum([row.count(0) for row in dp]))


### FIXED CODE ###

from collections import defaultdict

if __name__ == '__main__':
    MOD = 2019
    strS = input()
    S = [int(s) for s in strS]
    N = len(S)

    mods = defaultdict(int)
    mods[0] += 1
    pow10_mod = 1
    prv_mod = 0
    for idx, s in enumerate(S[::-1]):
        tmp_mod = (prv_mod + s * pow10_mod) % MOD

        mods[tmp_mod] += 1
        pow10_mod = (pow10_mod * 10) % MOD
        prv_mod = tmp_mod

    ans = 0
    for key, value in mods.items():
        if value >= 2:
            ans += value * (value - 1) // 2

    print(ans)