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

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

# 整数の入力
a = int(input())
# # スペース区切りの整数の入力
nums = list(map(int, input().split()))

vilist = []
for i in range(a):
    vilist.append((nums[i], i))
vilist = sorted(vilist, key=lambda vi: vi[0])

# dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
dp = []
for i in range(a):
    dp.append([0]*(a-i))

# dp = [[0] * a for i in range(a)]

# cnt = 0
# dp[i][j]を考える
for k in range(a-1):
    vi = vilist.pop()
    v = vi[0]
    p = vi[1]
    vi_z = vilist[0]
    vz = vi_z[0]
    pz = vi_z[1]
    for i in range(k + 2):
        # cnt += 1
        j = k - i + 1
        # if i == 0 and j == 0:
        #     continue

        # 最後の値は場所が特定できるのでそのまま計算させる
        if k == a - 2:
            if j == 0:
                dp[i][0] = dp[i-1][0] + v * abs(p - i + 1) + vz * abs(pz - i)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + v * abs(a - j - p) + vz * abs(a - j - 1 - pz)
            else:
                dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1) + vz * abs(pz - i),
                               dp[i][j-1] + v * abs(a - j - p) + vz * abs(pz - i))
        else:
            if j == 0:
                dp[i][0] = dp[i-1][0] + v * abs(p - i + 1)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + v * abs(a - j - p)
            else:
                dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1),
                               dp[i][j-1] + v * abs(a - j - p))

# print(cnt)
print(max([max(x) for x in dp]))


### FIXED CODE ###

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


def main():

    # 整数の入力
    a = int(input())
    # # スペース区切りの整数の入力
    nums = list(map(int, input().split()))

    vilist = []
    for i in range(a):
        vilist.append((nums[i], i))
    vilist = sorted(vilist, key=lambda vi: vi[0])

    # dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
    dp = []
    for i in range(a):
        dp.append([0]*(a-i))

    # dp = [[0] * a for i in range(a)]

    # cnt = 0
    # dp[i][j]を考える
    for k in range(a-1):
        vi = vilist.pop()
        v = vi[0]
        p = vi[1]
        vi_z = vilist[0]
        vz = vi_z[0]
        pz = vi_z[1]

        for i in range(k + 2):
            # cnt += 1
            j = k - i + 1
            # if i == 0 and j == 0:
            #     continue

            # 最後の値は場所が特定できるのでそのまま計算させる
            if k == a - 2:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1) + vz * abs(pz - i)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p) + vz * abs(a - j - 1 - pz)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1) + vz * abs(pz - i),
                                   dp[i][j-1] + v * abs(a - j - p) + vz * abs(pz - i))
            else:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1),
                                   dp[i][j-1] + v * abs(a - j - p))

    # print(cnt)
    print(max([max(x) for x in dp]))


main()
### BUGGY CODE ###

def solve():
    N = int(input())
    ans = []

    for i in range(N, 0, -1):
        sm = 0
        elems = []
        for k in range(i, 0, -1):
            if sm + k <= N:
                sm += k
                elems.append(k)
                if sm == N:
                    ans = elems
    print(*ans,sep='\n')

if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    N = int(input())
    ans = []

    left = 0
    right = N + 1
    while right - left > 1:
        mid = (left + right) // 2
        success, elems = calcElements(mid, N)
        if success:
            ans = elems
            right = mid
        else:
            left = mid
    print(*ans,sep='\n')

def calcElements(max_value, N):
    sm = 0
    elems = []
    for k in range(max_value, 0, -1):
        if sm + k <= N:
            sm += k
            elems.append(k)
            if sm == N:
                return (True, elems)
    
    return (False, elems)

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

import collections
import math
import operator as op
from functools import reduce

import numpy as np
import math
import bisect


def main():
    N = int(input())
    L = list(map(int, input().split()))

    L.sort()

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            a = L[i]
            b = L[j]

            # l = bisect.bisect_right(L[j+1:], abs(a-b))
            l = 0
            # print(l)
            r = bisect.bisect_left(L[j+1:], a+b)-1
            # candidates: [l, r]

            ans += max(0, r - l + 1)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections
import math
import operator as op
from functools import reduce

import numpy as np
import math
from bisect import bisect


def main():
    N = int(input())
    L = list(map(int, input().split()))

    L.sort()
    # M = [L[i] + L[j] for i in range(N) for j in range(i+1, N)]
    # M.sort()

    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):

            ans += bisect(L,L[i]+L[j]-1)-j-1

    print(ans)


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

s = input()
t = input()
s_num = len(s)
t_num = len(t)
dp = [[""] * (t_num + 1) for _ in range(s_num + 1)]

for i in range(s_num):
    for j in range(t_num):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i][j] + s[i], dp[i + 1][j], dp[i][j + 1], key=len)
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1], key=len)
print(dp[s_num][t_num])

### FIXED CODE ###

s = input()
t = input()
s_num = len(s)
t_num = len(t)
dp = [[0] * (t_num + 1) for _ in range(s_num + 1)]

for i in range(s_num):
    for j in range(t_num):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1])
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
ans = ""
i = s_num
j = t_num
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    elif dp[i][j] == dp[i - 1][j - 1] + 1:
        ans = s[i - 1] + ans
        i -= 1
        j -= 1
print(ans)
### BUGGY CODE ###

N, A, B = map(int, input().split())
S = input()
passed = []

for i in range(N):
  if S[i] == 'c':
    print('No')
  elif S[i] == 'a':
    if len(passed) < A+B:
      print('Yes')
      passed.append('a')
    else: print('No')
  else:
    if len(passed) < A+B and passed.count('b') < B:
      print('Yes')
      passed.append('b')
    else: print('No')

### FIXED CODE ###

n, a, b = map(int, input().split())
s = input().strip()

sumy = 0
sumf = 0
for _s in s:
  if _s == 'c':
    print('No')
  elif _s == 'a':
    if sumy < a + b:
      print('Yes')
      sumy += 1
    else:
      print('No')
  else:
    if sumy < a + b and sumf < b:
      print('Yes')
      sumy += 1
      sumf += 1
    else:
      print('No')
### BUGGY CODE ###

from collections import deque

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

ans = 0
perm = deque([(P[i]+1)/2.0 for i in range(K-1)])

for i in range(K-1, N):
    perm.append((P[i]+1)/2.0)
    if ans < sum(perm):
        ans = sum(perm)
    perm.popleft()

print(ans)


### FIXED CODE ###

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

cml_sum = [(P[0]+1)/2.0]
for i in range(1, N):
    cml_sum.append(cml_sum[i-1] + (P[i]+1)/2.0)

ans = cml_sum[K-1]
for i in range(N-K):
    target = cml_sum[i+K] - cml_sum[i]
    if ans < target:
        ans = target

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

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

x = 0
n = int(input())+1

for i in range(1,n):
    for j in range(1, n):
        for k in range(1, n):
            x += gcd(i,j,k)

print(x)

### FIXED CODE ###

from math import gcd

x = 0
n = int(input())+1
 
for i in range(1,n):
    for j in range(1, n):
        for k in range(1, n):
            x += gcd(gcd(i,j), k)
 
print(x)
### BUGGY CODE ###

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

ac = 1
for i in range(K):
    ac *= A[i]

pre = ac
for i in range(K, N):
    ac = (ac // A[i - K]) * A[i]
    if pre < ac: print('Yes')
    else: print('No')
    pre = ac





### FIXED CODE ###

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

for i in range(K, N):
    if A[i-K] < A[i]: print('Yes')
    else: print('No')
### BUGGY CODE ###


from sys import stdin
import itertools

n = int(stdin.readline().rstrip())
ls = [int(x) for x in stdin.readline().rstrip().split()]

ans = 0
for v in itertools.combinations(ls, 3):
    #print(v)
    a=int(v[0])
    b=int(v[1])
    c=int(v[2])
    if a<b+c:
        if b<c+a:
            if c<a+b:
                ans += 1
            else:
                continue
        else:
            continue
    else:
        continue

print(int(ans))


### FIXED CODE ###

from sys import stdin
from collections import defaultdict, deque, Counter
import sys
from bisect import bisect_left
import heapq
import math

sys.setrecursionlimit(1000000000)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

n = int(stdin.readline().rstrip())
l = list(map(int, stdin.readline().rstrip().split()))
#A, B, C = map(int, stdin.readline().rstrip().split())
#S = [list(stdin.buffer.readline().decode().rstrip()) for _ in range(h)]

l.sort()
ans = 0

for i in range(n):
    for j in range(i+1, n):
        t = l[i] + l[j]
        idx = bisect_left(l,t)
        ans += max(0,idx-j-1)

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

from collections import Counter


def check(a, b):
    for ai, bi in zip(a, b):
        if ai == bi:
            return True
    return False


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    b = [int(i) for i in input().split()]
    ca = Counter(a)
    cb = Counter(b)
    for k in cb.keys():
        if cb[k] > n - ca[k]:
            print("No")
            return
    shift = max(ca[k] for k in cb.keys())
    while check(a, b):
        b = b[shift:] + b[:shift]
    print("Yes")
    print(*b)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter
import numpy as np


def main():
    n = int(input())
    a = np.array([int(i) for i in input().split()])
    b = np.array([int(i) for i in input().split()])
    ca = Counter(a)
    cb = Counter(b)
    for k in cb.keys():
        if cb[k] > n - ca[k]:
            print("No")
            return
    while any(a == b):
        s = max(ca[k] for k in cb.keys())
        b = np.roll(b, s)
    print("Yes")
    print(*b)


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

n = input()
dishes = []
for i in range(int(n)):
    tmp = [int(each) for each in input().split()]
    dishes.append((abs(tmp[0] - tmp[1]), tmp[0], tmp[1]))

dishes = sorted(dishes, key=lambda x: x[0], reverse=True)

point = [0, 0]
player = 0
while len(dishes) > 0:
    tmp_point = -1
    dish = None
    for tmp_dish in dishes:
        if dish is None:
            dish = tmp_dish
        elif tmp_point > dish[0]:
            break
        else:
            if dish[player + 1] > tmp_dish[player + 1] and tmp_dish[player + 1] - tmp_dish[int(not player) + 1] >= 0:
                dish = tmp_dish
            else:
                pass
    dishes.remove(dish)
    point[player] += dish[player + 1]
    player = int(not player)
print(point[0] - point[1])

### FIXED CODE ###

n = input()
dishes = []
for i in range(int(n)):
    tmp = [int(each) for each in input().split()]
    dishes.append((abs(tmp[0] + tmp[1]), tmp[0], tmp[1]))

dishes = sorted(dishes, key=lambda x: x[0], reverse=True)

point = [0, 0]
player = 0
while len(dishes) > 0:
    dish = dishes.pop(0)
    point[player] += dish[player + 1]
    player = int(not player)
print(point[0] - point[1])
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
l_li=[]
r_li=[]
for i in range(q):
    l,r=map(int,input().split())
    l_li.append(l)
    r_li.append(r)
    
dp =[[0 for i in range(n+2)] for j in range(n+2)]

for i in range(1):
    for j in range(i,n):
        t=0
        if s[j]=="C" and j!=0:
            if s[j-1]=="A":
                t=1
        
        dp[i][j]=dp[i][j-1]+t
        
for i in range(1,n):
    t=0
    if s[i]=="C" and s[i-1]=="A":   
        dp[i][i:n]=list(map(lambda x: x-1,dp[i-1][i:n]))
    else:
        dp[i][i:n]=dp[i-1][i:n]       
        
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
    
dp =[0 for j in range(n)]


for j in range(n):
    t=0
    if s[j]=="C" and j!=0:
        if s[j-1]=="A":
            t=1

    dp[j]=dp[j-1]+t
        

for i in range(q):
    l,r=map(int,input().split())
    print(dp[r-1]-dp[l-1])
### BUGGY CODE ###

import re
n,q=map(int,input().split())
s=input()
a=[m.span() for m in re.finditer("AC", s)]

for _ in range(q):
  l,r=map(int,input().split())
  ans=sum(1 for x in a if l-1<=x[0] and x[1]<=r)
  print(ans)


### FIXED CODE ###

import re
import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=input()
a=[0]*(n+1)
tmp=0
for i in range(n-1):
  if s[i:i+2]=="AC":
    tmp+=1
  a[i+2]=tmp

for _ in range(q):
  l,r=map(int,input().split())
  print(a[r]-a[l])
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
if n>=24:
    print(0)
    exit()
op=[[0],[1]]
for i in range(n-1):
    tmp=[]
    for j in op:
        tmp.append(j+[0])
        tmp.append(j+[1])
    op=tmp
ans=0
for i in op:
    t=[0]
    for j in range(n):
        if i[j]==0:
            t.append(d[j])
        else:
            t.append(24-d[j])
    a=10000
    for p in range(1,1+n):
        for q in range(p):
            b=abs(t[p]-t[q])
            a=min(a,min(b,24-b))
    ans=max(ans,a)
print(ans)


### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
if n>=24:
    print(0)
    exit()
if n>=22:
    t=[]
    d.append(0)
    d.sort()
    f=1
    for i in range(n):
        if d[i]==d[i+1]:
            f+=1
        else:
            if f>2:
                print(0)
                exit()
            f=1
    print(1)
    exit()

op=2**n-1
ans=0
for i in range(op):
    t=[0]
    for j in range(n):
        if i&(2**j)>0:
            t.append(d[j])
        else:
            t.append(24-d[j])
    a=10000
    for p in range(1,1+n):
        for q in range(p):
            b=abs(t[p]-t[q])
            a=min(a,min(b,24-b))
    ans=max(ans,a)
print(ans)
### BUGGY CODE ###

import itertools

n = int(input())
l = list(map(int,input().split()))

combinations = list(itertools.combinations(range(n),3))

c = 0

for i in combinations:
    if l[i[0]] < l[i[1]] + l[i[2]] and l[i[1]] < l[i[0]] + l[i[2]] and l[i[2]] < l[i[1]] + l[i[0]]:
        c += 1
    
print(c)


### FIXED CODE ###

import itertools
import bisect

n = int(input())
l = list(map(int,input().split()))

l = sorted(l)

combinations = list(itertools.combinations(range(n),2))

cnt = 0

for i in combinations:
    a_b = l[i[0]] + l[i[1]]
    max_ab = max(i[0], i[1])
    c = bisect.bisect_left(l,a_b)
    
    cnt += (c - (max_ab+1))


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

n = int(input())
s = input()
r_count = s.count('R')
g_count = s.count('G')
b_count = s.count('B')

count=0
for i in range(n):
    for j in range(i+1,n):
        if (2*j-i)>(n-1):
            continue
        if s[i]!=s[j]!=s[2*j-i] and s[j]!=s[2*j-i] and s[i]!=s[2*j-i]:
            count+=1
print(r_count*g_count*b_count-count)

### FIXED CODE ###

n = int(input())
s = input()
r_count = s.count('R')
g_count = s.count('G')
b_count = s.count('B')

count=0
for i in range(n):
    a = s[i]
    for j in range(i+1,n):
        if (2*j-i)>(n-1):
            continue
        b=s[j]
        c=s[2*j-i]
        if a!=b and b!=c and a!=c:
            count+=1
print(r_count*g_count*b_count-count)
### BUGGY CODE ###

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


max_magic = 0
for a, _ in magic:
    max_magic = max(max_magic, a)

amount = H + 1
dp = [0] * (amount + max_magic)
dp[0] = 0

ret = float('inf')

for amt in range(1, amount + max_magic):
    t = [dp[amt - a] + b if amt - a >= 0 else float('inf') for a, b in magic]
    dp[amt] = min(t)

    if amt >= H:
        ret = min(dp[amt], ret)

print(ret)


### FIXED CODE ###

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


max_magic = 0
for a, _ in magic:
    max_magic = max(max_magic, a)

amount = H + 1
dp = [0] * (amount + max_magic)
dp[0] = 0

ret = float('inf')

for amt in range(1, amount + max_magic):
    t = [dp[amt - a] + b for a, b in magic]
    dp[amt] = min(t)

    if amt >= H:
        ret = min(dp[amt], ret)

print(ret)
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,K = list(map(int, input().split()))
h = list(map(int, input().split()))

# suml = [1e9 for i in range(N)]
# suml[0] = 0
suml = [0]*N

for e in range(1,N):

    # for k in range(1, min([e, K])+1):
    #     suml[e] = min(suml[e],
    #             abs(h[e]-h[e-k]) + suml[e-k]
    #     )
    start = max(0, e-K)
    cost  = min(cst + abs( h[e] - hgh ) for cst, hgh in zip(suml[start:e], 
           h[start:e]))
    suml[e] = cost

print(suml[N-1])
        



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# N,K = list(map(int, input().split()))
# h = list(map(int, input().split()))

# (N,K), h = map(int, input().split()), list(map(int, input().split()))
N,K,*h = map(int, "\n".join([input(), input()]).split())

# suml = [1e9 for i in range(N)]
# suml[0] = 0


suml = [0]*N

# for i in range(1,N):
for i,e_h in enumerate(h):
    if i == 0:
        continue

    start = max(0, i-K)
    cost  = min(cst + abs( e_h - hgh) for cst, hgh in 
                   zip(suml[start:i], h[start:i]))
    # cost  = min(cst + abs( h[i] - hgh ) for cst, hgh in 
    #               zip(suml[start:i], h[start:i]))
    suml[i] = cost

print(suml[-1])
### BUGGY CODE ###

N , W = map(int , input().split())
weight = []
value = []
for _ in range(N):
    w , v = map(int , input().split())
    weight.append(w)
    value.append(v)

def knapsack():
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    def solve(i,w):
        if N == i:
            ret_val = 0
        elif w - weight[i] < 0:
            ret_val = solve(i + 1,w)
        else:
            ret_val = max(solve(i + 1, w), solve(i + 1,w - weight[i]) + value[i])
        dp[i][w] = ret_val
        return dp[i][w]
    solve(0,W)
    #print(dp)
    return max(dp[0])

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

### FIXED CODE ###

import numpy as np
N , W = map(int, input().split())
goods = np.array([list(map(int , input().split())) for _ in range(N)])
dp = np.zeros((N + 1 , W + 1) , dtype = np.int)

for i in range(0,N):
    w, v = goods[i,:]
    dp[i + 1, w:] = np.maximum(dp[i,w:] , dp[i,:-w] + v)
    dp[i + 1, :] = np.maximum(dp[i + 1,:],dp[i,:])
print(int(dp[N,W]))
### BUGGY CODE ###

"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
from collections import deque, defaultdict, Counter
import math
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


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

# a/b の切り上げ


def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def main():
    s = input()[::-1]

    cnt = [0] * 2019
    # print(cnt)
    cnt[0] = 1
    ans = 0
    b = 0
    t = 1
    for c in s:
        b = b + int(c) * t
        amari = b % 2019
        cnt[amari] += 1
        t *= 10

    for i in range(2019):
        ans += cnt[i] * (cnt[i] - 1) // 2
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

s = input()[::-1]

sum_of_digits = 0

cnts = [0] * 2019

cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

ans = 0

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

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

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

            else:

                flg = 0
    finally:

        return array_result

arr_data = getinputdata()

n = int(arr_data[0][0])
k = int(arr_data[0][1])

arr = [int(x) for x in arr_data[1]]
mindata = min(arr)
arr_replace = [mindata for x in range(k)]

cnt = 0
idx = 0

while not (all(x == mindata for x in arr)):
    
    if not(all(x == mindata for x in arr[idx:idx + k])):
        cnt += 1
        arr[idx:idx + k] = arr_replace
    
    if not(all(x == mindata for x in arr[idx + k-1:idx + k-1 + k])):
        cnt += 1
        arr[idx + k-1:idx + k-1 + k] = arr_replace
    
    idx += k-1 + k-1
    
#    print(arr,idx)
#    print(arr[idx:idx+k])
#    print(arr[idx+k-1:idx+k-1+k])
    
print(cnt) 
    
    
    


### FIXED CODE ###

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

            else:

                flg = 0
    finally:

        return array_result

arr_data = getinputdata()

n = int(arr_data[0][0])
k = int(arr_data[0][1])

arr = [int(x) for x in arr_data[1]]

cnt=1
if n <= k:
    
    print(cnt)
    
else:
    
    chkflg = True
    
    while chkflg:
        
        cnt+=1

        s = k + 1 + (k-1) * (cnt-2)
        e = k * 2-1 + (k-1) * (cnt-2)
        
        if s<=n<=e:
            
            chkflg=False
            
            
    print(cnt)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = str(input())
for i in range(0,Q):
 l,r = map(int,input().split())
 slice = S[l-1:r]
 cnt = slice.count("AC")
 print(cnt)


### FIXED CODE ###

N,Q = map(int,input().split())
S = (input())
cnt = [0] * (N + 1)
for i in range(N):
 if S[i:i+2] == "AC":
  cnt[i+1] = cnt[i] + 1
 else:
  cnt[i+1] = cnt[i]

for i in range(0,Q):
 l,r = map(int,input().split())
 print(cnt[r-1] - cnt[l-1])