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

def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    L = [0 for i in range(n1+1)]
    R = [0 for i in range(n2+1)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = float('inf')
    R[n2] = float('inf')
    i = 0
    j = 0
    global cnt

    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        
        else:
            A[k] = R[j]
            j = j+1
    return cnt

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         mergeSort(A, left, mid)
         mergeSort(A, mid, right)
         merge(A, left, mid, right)
    else:
        return 0

n = input()
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, len(A))
print(*A)
print(str(cnt))

### FIXED CODE ###

def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    #L = [0 for i in range(n1+1)]
    #R = [0 for i in range(n2+1)]
    #for i in range(n1):
    #    L[i] = A[left+i]
    #for i in range(n2):
    #    R[i] = A[mid+i]
    L = A[left:mid]
    R = A[mid:right]
    L.append(float('inf'))
    R.append(float('inf'))
    i = 0
    j = 0
    global cnt

    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        
        else:
            A[k] = R[j]
            j = j+1
    return cnt

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         mergeSort(A, left, mid)
         mergeSort(A, mid, right)
         merge(A, left, mid, right)
    else:
        return 0

n = input()
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, len(A))
print(*A)
print(str(cnt))
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = abs(a[0] - (sum(a) - a[0]))
for i in range(2, N):
    tmp = abs(sum(a[i:]) - sum(a[:i]))
    if (ans > tmp):
        ans = tmp
print(ans)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
X = sum(a)
x = a[0]
ans = abs(X - 2*x)
for i in range(1, N-1):
    x += a[i]
    tmp = abs(X-2*x)
    if (ans > tmp):
        ans = tmp
print(ans)
### BUGGY CODE ###

import re
S = input()
N = len(S)
for _ in range(N//2):
    S = re.sub("01|10","",S)
else:
  print(N-len(S))

### FIXED CODE ###

S = input()
N = len(S)
print(2*min(S.count("0"),S.count("1")))
### BUGGY CODE ###

n = int(input())

a = list(map(int,input().split()))

ans = 1
for i in a:
    ans = ans * i

if ans > 10**18:
    print(-1)
else:
    print(ans)
    

### FIXED CODE ###

n = int(input())

a = list(map(int,input().split()))

ans = 1

if 0 in a:
    ans = 0
else:
    for i in a:
        if ans <= 10**18:
            ans = ans * i
        else:
            break

if ans > 10**18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

cost = {}#[[float('inf')]*(m+1) for i in range(n+1)]
#Aからi冊、Bからｊ冊読むときにかかる時間がcost[i][j]
              
cost[(0,0)] = 0
max_count = 0

i = 0
while i<=n:
  j = 0
  while j<m:
    cost[(i,j+1)] = cost[(i,j)] + b[j]
    j += 1
    if cost[(i,j)]<=k:
      max_count = max(max_count,i+j)
    else:
      break
  if i == n:
    break
  cost[(i+1,0)] = cost[(i,0)] + a[i]
  i += 1
  if cost[(i,0)]<=k:
    max_count = max(max_count,i)
  else:
    break
print(max_count)

### FIXED CODE ###

def judge(num):
  if num>n+m:
    return False
  for i in range(max(0,num-m),min(n,num)+1):
    if a_cumsum[i] + b_cumsum[num-i]<=k:
      return True
  return False
 
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
 
a_cumsum = [0]
b_cumsum = [0]
for i in a:
  a_cumsum.append(a_cumsum[-1]+i)
for i in b:
  b_cumsum.append(b_cumsum[-1]+i)
  
left = 0
right = k+1
 
while right-left>1:
  mid = (right+left)//2
  
  if judge(mid):
    left = mid
  else:
    right = mid
 
print(left)
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    import numpy as np

    N, K = map(int, input().split())
    H = np.array(input().split(), 'int32')

    INF = 10 ** 10
    dp = np.full(N, INF, 'int64')
    dp[0] = 0
    for i in range(N):
        target = dp[i]
        now_height = H[i]
        for k in range(1, K + 1 if i + K < N else N - i):
            res = target + abs(now_height - H[i + k])
            cal = dp[i + k]
            dp[i + k] = res if res < cal else cal
        # right = min(i + K, N)
        # dp[i + 1:right] = np.min(dp[i] + np.abs(H[i] - H[i + 1:right]))
    print(dp[N - 1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def resolve():
    import sys
    
    readline = sys.stdin.readline

    N, K = map(int, readline().split())
    h = [int(x) for x in readline().split()]

    inf = float('inf')
    dp = [inf] * N
    dp[0] = 0

    for i in range(1, N):
        leng = i + 1 if i < K else K + 1
        for j in range(leng):
            cal = dp[i - j] + abs(h[i] - h[i - j])
            if dp[i] > cal:
                dp[i] = cal

    print(dp[-1])
            

resolve()
### BUGGY CODE ###

def main():
    k = int(input())
    s = input()
    n = len(s)

    def cmb1(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 = 2*10**6+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 )

    def power(a, n, mod):
        bi=str(format(n,"b")) #2進数
        res=1
        for i in range(len(bi)):
            res=(res*res) %mod
            if bi[i]=="1":
                res=(res*a) %mod
        return res

    ans = 0
    for i in range(k+1):
        temp = power(25, i, mod)
        temp *= cmb1(i+n-1, n-1, mod)
        temp %= mod
        temp *= power(26, k-i, mod)
        temp %= mod
        ans += temp
    print(ans%mod)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    k = int(input())
    s = input()
    n = len(s)

    def cmb1(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 = 2*10**6
    fac = [1]*(N+1)
    finv = [1]*(N+1)
    for i in range(N):
        fac[i+1] = fac[i] * (i+1) % mod
    finv[-1] = pow(fac[-1], mod-2, mod)
    for i in reversed(range(N)):
        finv[i] = finv[i+1] * (i+1) % mod

    def cmb1(n, r, mod):
        if r <0 or r > n:
            return 0
        r = min(r, n-r)
        return fac[n] * finv[r] * finv[n-r] % mod

    def power(a, n, mod):
        bi=str(format(n,"b")) #2進数
        res=1
        for i in range(len(bi)):
            res=(res*res) %mod
            if bi[i]=="1":
                res=(res*a) %mod
        return res

    ans = 0
    for i in range(k+1):
        temp = power(25, i, mod)
        temp *= cmb1(i+n-1, n-1, mod)
        temp %= mod
        temp *= power(26, k-i, mod)
        temp %= mod
        ans += temp
    print(ans%mod)

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

x = int(input())
t = 0
i = 0
while t < x:
    t = int(t*(1.01))
    i += 1

print(ans)

### FIXED CODE ###

x = int(input())
t = 100
i = 0
while t < x:
    t = int(t*(1.01))
    i += 1
 
print(i)
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
d=dict()
for i in range(1000):
  num='0'*(3-len(str(i)))+str(i)
  for j in range(n-2):
    if s[j]==num[0]:
      for k in range(j+1,n-1):
        if s[k]==num[1]:
          for l in range(k+1,n):
            if s[l]==num[2]:
              if num not in d:
                ans+=1
                d[num]=0
            if l==n-1:
              break
        if k==n-2:
          break
    if j==n-3:
      break
print(ans)


### FIXED CODE ###

n=int(input())
s=input()
cnt=0
for i in range(1000):
  l=(3-len(str(i)))*'0'+str(i)
  if l[0] in s:
    p1=s.index(l[0])
    if l[1] in s[p1+1:]:
      p2=p1+s[p1+1:].index(l[1])+1
      if l[2] in s[p2+1:]:
        cnt+=1
print(cnt)
### BUGGY CODE ###

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

list_xst = []
for _ in range(n):
    s,t,x = list(map(int, input().split()))
    list_xst.append([x, s-x, t-x])

list_xst.sort()

list_d = []
for _ in range(q):
    list_d.append(int(input()))

for d in list_d:
    retn = -1
    for xst in list_xst:
        if ( (xst[1] <= d) and (xst[2] > d) ):
            retn = xst[0]
            break
    print(retn)

### FIXED CODE ###

import bisect

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

list_xst = []
for _ in range(n):
    s,t,x = list(map(int, input().split()))
    list_xst.append([x, s-x, t-x])

list_xst.sort(key=lambda l:l[0])

list_d = [int(input()) for _ in range(q)]

retn = [-1] * q
jmp = [-1] * q

for x,s,t in list_xst:
    i = bisect.bisect_left(list_d, s)
    tt = bisect.bisect_left(list_d, t)
    while i < tt:
        if (jmp[i] != -1):
            i = jmp[i]
        else:
            retn[i] = x
            jmp[i] = tt
            i += 1

print(*retn, sep="\n")
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    dq = [LI() for _ in range(N)]
    p = [0] * N
    cnt = 0
    c = [0] * N
    while cnt < N*(N-1)//2:
        ud = False
        for i in range(N):
            if p[i] >= N-1: continue

            j = dq[i][p[i]]-1
            if dq[j][p[j]]-1 == i:
                c[i] = c[j] = max(c[i],c[j]) + 1
                p[i] += 1; p[j] += 1
                cnt += 1
                ud = True
        if ud:
            continue
        else:
            print(-1)
            return
    print(max(c))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    dq = [LI() for _ in range(N)]
    p = [0] * N
    cnt = 0
    c = [0] * N
    while cnt < N*(N-1)//2:
        ud = False
        for i in range(N):

            while p[i] < N-1:
                j = dq[i][p[i]]-1
                if dq[j][p[j]]-1 == i:
                    c[i] = c[j] = max(c[i],c[j]) + 1
                    p[i] += 1; p[j] += 1
                    cnt += 1
                    ud = True
                else:
                    break
        if ud:
            continue
        else:
            print(-1)
            return
    print(max(c))

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

N = int(input())
S = []
CNT = []
for i in range(N):
    dummy = input()
    S.append(dummy)
    CNT.append(S.count(S[i]))
MAX = max(CNT)
new_S = []
for i in range(N):
    if (CNT[i] == MAX and S[i] not in new_S):
        new_S.append(S[i])
new_S = sorted(new_S)
for x in new_S:
    print(x)

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())
S = sorted(S)
CNT = [1]
dummy = 1
for i in range(1, N):
    if(S[i] == S[i - 1]):
        dummy += 1
    else:
        dummy = 1
    CNT.append(dummy)
#print(S)
#print(CNT)        
MAX = max(CNT)
for i in range(N):
    if(CNT[i] == MAX):
        print(S[i])
### BUGGY CODE ###

N, K = map(int, input().split())
P = [int(p) for p in input().split()]
P_kitai = [(1 + p)/2 for p in P]

max_kitai = 0
for i in range(N - K + 1):
    res = sum(P_kitai[i:i+K])
    max_kitai = max(max_kitai, res)
print(max_kitai)

### FIXED CODE ###

N, K = map(int, input().split())
P = [int(p) for p in input().split()]
P_kitai = [(1 + p)/2 for p in P]

max_kitai = 0
res = 0
for i in range(N - K + 1):
    if i == 0: 
        res = sum(P_kitai[i:i+K])
    else:
        res = res - P_kitai[i-1] + P_kitai[i+K-1]
    max_kitai = max(max_kitai, res)
print(max_kitai)
### BUGGY CODE ###

import itertools

def main():
    N = int(input())
    base_list=input().split()
    int_list=[]
    i = 0
    [int_list.append(int(i)) for i in base_list]
    int_list=sorted(int_list)
    anslist=list(itertools.combinations(int_list,3))
    ans=0
    for t in anslist:
        if t[0] < (t[1]+t[2]) and t[1] < (t[2]+t[0]) and t[2] < (t[0]+t[1]):
            ans+=1
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import bisect

def main():
    N = int(input())
    base_list=input().split()
    int_list=[]
    i = 0
    [int_list.append(int(i)) for i in base_list]
    int_list=sorted(int_list)
    anslist=[]
    ans=0
    for index,value in enumerate(int_list):
        for index2,value2 in enumerate(int_list[index+1:]):
            ans+=bisect.bisect_left(int_list,value+value2)-(index+1+index2+1)
    print(ans)

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

n=int(input())
l=[]
c=0
for i in range(n):
    s=str(input())
    if(s not in l):
        l.append(s)
        c=c+1
print(c)

### FIXED CODE ###

n=int(input())
d=set()
for i in range(n):
    s=str(input())
    d.add(s)
print(len(d))
### BUGGY CODE ###

# coding: utf-8
from pdb import set_trace

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

if N<3:
    print(0)
    exit()
LN = [i for i in range(N)]
cnt = []
for xa, a in enumerate(L[:-2]):
    for xb, b in enumerate(L[xa+1:-1]):
        for xc, c in enumerate(L[xa+2:]):
            if a+b>c and b+c>a and c+a>b and a!=b and b!=c and c!=a:
                li = sorted([xa, xb+xa+1, xc+xa+2])
                flag = True
                for _cnt in cnt:
                    if _cnt==li:
                        flag = False
                if flag:
                    cnt.append(li)
print(len(cnt))

### FIXED CODE ###

# coding: utf-8
from pdb import set_trace
#from collections import Counter
import itertools

N = int(input())
L = list(map(int, input().split(" ")))
# print(L)

# C = dict(Counter(L))
# L = sorted(list(set(L)), reverse=True)

# if N<3 or len(L)<3:
#     print(0)
#     exit()
# li = []
# for xa, a in enumerate(L[:-2]):
#     for xb, b in enumerate(L[xa+1:-1]):
#         for xc, c in enumerate(L[xa+2:]):
#             if a+b<c:
#                 break
#             if a+b>c and b+c>a and c+a>b and a!=b and b!=c and c!=a:
#                 _li = sorted([xa, xb+xa+1, xc+xa+2])
#                 if _li in li:
#                     continue
#                 li.append(_li)
# cnt = 0
# for l in li:
#     a = C[L[l[0]]]
#     b = C[L[l[1]]]
#     c = C[L[l[2]]]
#     cnt += (a * b * c)
# print(cnt)
cnt = 0
TRI = list(itertools.combinations(L, 3))
for tri in TRI:
    a, b, c = tri
    if a==b or b==c or c==a:
        continue
    elif a+b>c and a+c>b and b+c>a:
        cnt += 1
print(cnt)
### BUGGY CODE ###

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

mod=10**9+7
sum=0
for i in range(N-1):
    for j in range(i+1,N):
        A[i]=A[i]%mod
        A[j]=A[j]%mod
        sum+=((A[i])*(A[j] ))
        sum=sum%mod
print(sum)

### FIXED CODE ###

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

mod=10**9+7

B=[0]
for i in range(1,N+1):
    B.append(A[i-1]+B[i-1])

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

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

n = int(input())
s = input()

result = []

for i in range(n):
    left = list(s[:i])
    right = list(s[i+1:])

    cnt1 = left.count('W')
    cnt2 = right.count('E')

    result.append(cnt1 + cnt2)

print(min(result))
    

### FIXED CODE ###

n = int(input())
s = input()

w = [0]
e = [0]

tmp_w = 0
tmp_e = 0

for i in range(1, n):

    j = (n - 1) - i

    if (s[i-1] == 'W'):
        w.append(tmp_w + 1)
        tmp_w += 1
    else:
        w.append(tmp_w)

    if (s[j+1] == 'E'):
        e.append(tmp_e + 1)
        tmp_e += 1
    else:
        e.append(tmp_e)

e.reverse()

ans = 10 ** 6 
for i in range(n):
    ans = w[i] + e[i] if w[i] + e[i] < ans else ans

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

N = int(input())

coins = list(map(float, input().split()))

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

dp[0][0] = 1 - coins[0]
dp[0][1] = coins[0]

for j in range(1, N):
    for h in range(N+1):
        if h == 0:
            dp[j][h] = (1 - coins[j]) * dp[j-1][0]
        else:
            dp[j][h] = (1 - coins[j]) * dp[j-1][h] + coins[j] * dp[j-1][h-1]

print(sum(dp[-1][head] for head in range(N//2 + 1, N+1)))


### FIXED CODE ###

N = int(input())

coins = list(map(float, input().split()))

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

dp[0][0] = 1 - coins[0]
dp[0][1] = coins[0]

for j in range(1, N):
    for h in range(j+2):
        if h == 0:
            dp[j][h] = (1 - coins[j]) * dp[j-1][0]
        else:
            dp[j][h] = (1 - coins[j]) * dp[j-1][h] + coins[j] * dp[j-1][h-1]
     
print(sum(dp[-1][head] for head in range(N//2 + 1, N+1)))
### BUGGY CODE ###

from itertools import combinations

N, X, Y = map(int, input().split())

for k in range(1, N):
    count = 0
    for i, j in combinations(range(1, N+1), 2):
        if min(j - i, abs(X-i)+1+abs(Y-j)) == k:
            count += 1
    print(count)


### FIXED CODE ###

from collections import Counter
from itertools import combinations

N, X, Y = map(int, input().split())

C = Counter(min(j - i, abs(X - 1 - i) + 1 + abs(Y - 1 - j)) for i, j in combinations(range(N), 2))

for i in range(1, N):
  print(C[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
line = input().split(" ")
n = int(line[0])
a = int(line[1])
x = [int(i) for i in input().split(" ")]

X = max(max(x), a)

dp = [[[0 for s in range(n*X+1)] for k in range(n+1)] for j in range(n+1)]

dp[0][0][0] = 1

for j in range(n+1):
    for k in range(n+1):
        for s in range(n*X+1):
            if j>0 and s<x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            elif j>0 and k>0 and s>=x[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]

ret = 0
for k in range(1,n+1):
    ret += dp[n][k][k*a]
print(ret)


### FIXED CODE ###

n,a = map(int, input().split())
xl = list(map(int, input().split()))

offset = 300
dp = [[0]*600 for _ in range(n+1)]
dp[0][offset] = 1
for i in range(1,n+1):
    x = xl[i-1]-a
    for j in range(-300,300):
        dp[i][offset+j] = dp[i-1][offset+j]
        if 600>offset+j-x>=0:
            dp[i][offset+j] += dp[i-1][offset+j-x]

print(dp[n][offset]-1)
### BUGGY CODE ###

from collections import defaultdict
N,Ma,Mb=map(int,raw_input().split())
A=[]
B=[]
C=[]
a_sum=0
b_sum=0
for i in range(N):
	a,b,c=map(int,raw_input().split())
	A.append(a)
	B.append(b)
	C.append(c)
	a_sum+=a
	b_sum+=b

dp=defaultdict(lambda: float("inf"))
dp[(0,0,0)]=0


for k in range(1,N+1):
	for x in range(a_sum+1):
		for y in range(b_sum+1):
			dp[(k,x,y)]=min( dp[(k,x,y)], dp[(k-1,x,y)] )
			if x-A[k-1]>=0 and y-B[k-1]>=0:
				dp[(k,x,y)]=min( dp[(k-1,x,y)], dp[(k-1, x-A[k-1], y-B[k-1])]+C[k-1] )


ans=float("inf")
for x in range(1,a_sum+1):
	for y in range(1,b_sum+1):
		if x*Mb==y*Ma:
			ans=min(ans,dp[(N, x, y)])

if ans==float("inf"):
	print -1
else:
	print ans
			

### FIXED CODE ###

from collections import defaultdict
N,Ma,Mb=map(int,raw_input().split())

dp=defaultdict(lambda: float("inf"))
dp[(0,0)]=0

for i in range(N):
	a,b,c=map(int,raw_input().split())
	for j in dp.items():
		x=j[0][0]
		y=j[0][1]
		z=j[1]
		na, nb, nc = x+a, y+b, z+c 
		dp[(na, nb)]=min( dp[(na, nb)], nc)


ans=float("inf")
for i in dp.items():
	x=i[0][0]
	y=i[0][1]
	z=i[1]
	if x==0 and y==0:
		continue
	if x*Mb==y*Ma:
		ans=min(ans,z)

else:
	if ans==float("inf"):
		print -1
	else:
		print ans
### BUGGY CODE ###

N=int(input())
A=[int(input()) for x in range(N)]
y=list()
for i in A:
    if i in y:
        y.remove(i)
    else:
        y.append(i)
print(len(y))


### FIXED CODE ###

N=int(input())
A=[int(input()) for x in range(N)]
y=set()
for i in A:
    if i in y:
        y.remove(i)
    else:
        y.add(i)
print(len(y))
### BUGGY CODE ###

def main():
    n = int(input())
    p = [i for i in range(1, n+1)]

    ans = 0
    for i in range(n-1):
        ans += p[i] % (p[i]+1)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

    ans = n * (n-1)//2
    print(ans)


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

S = input()
while 1:
    for key_word in ["erase", "eraser", "dream", "dreamer"]:
        if S.endswith(key_word):
            S = S[:-len(key_word)]
            break
        else:
            print("NO")
            break
        if not query:
            print("YES")
            break

### FIXED CODE ###

s = input()
s = s.replace('eraser', '')
s = s.replace('erase', '')
s = s.replace('dreamer', '')
s = s.replace('dream', '')
if s:
  print('NO')
else:
  print('YES')
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

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

needs = [0,2,5,5,4,5,6,3,7,6]
need_to_ch = {}
for a in sorted(As):
    need = needs[a]
    need_to_ch[need] = str(a)

ans = 0
needs = list(need_to_ch.keys())
def dfs(idx, remain, used):
    global ans
    need = needs[idx]
    if idx == len(needs) - 1:
        if remain % need:
            return
        used += [remain // need]
        s = ''
        for (n, ch), use in zip(need_to_ch.items(), used):
            s += ch * use
        ans = max(ans, int(''.join(sorted(s, reverse=True))))
    else:
        for i in range(0, remain + 1, need):
            dfs(idx + 1, remain - i, used + [i // need])
dfs(0, N, [])
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 自力実装できず
#
# 解説PDFが理解できなかったので
# http://drken1215.hatenablog.com/entry/2019/02/16/224100
# を参考に実装

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys


def str_max(s1, s2):
    if len(s1) > len(s2):
        return s1
    elif len(s1) < len(s2):
        return s2
    if s1 > s2:
        return s1
    else:
        return s2


def main():
    N, M = map(int, input().split())
    As = list(map(int, input().split()))
    
    needs = [0,2,5,5,4,5,6,3,7,6]
    need_to_ch = {}
    for a in sorted(As):
        need = needs[a]
        need_to_ch[need] = str(a)
    
    dp = [None for _ in range(N + 1)]
    dp[0] = ''
    for i in range(1, N + 1):
        for need, ch in need_to_ch.items():
            if i - need < 0 or dp[i - need] is None:
                continue
            cand = dp[i - need] + ch
            if dp[i] is None:
                dp[i] = cand
            else:
                dp[i] = str_max(dp[i], cand)
        # print("dp[{}] = {}".format(i, dp[i]))
    print(dp[N])


main()
### BUGGY CODE ###

# D
# Multiple of 2019

s = input()

d = len(s)

ans = 0

if d < 5:
    if int(s)%2019 == 0:
        print("1")
    else:
        print("0")
else:
    for j in range(4,d,1):
        for i in range(j-3):
            _tmp = int(s[i:j+1])
            if _tmp % 2019 == 0:
                ans +=1

    print(ans)

### FIXED CODE ###

# D
# Multiple of 2019
import itertools

s = input()[::-1]

d = len(s)

# _list = [None]*d
_map = [0]*2019
_map[0] = 1

ans = 0
j,_ = 1,0

for i in s:
    _ += int(i) * j
    _tmp = _ % 2019
    j = (j*10)%2019
    _map[_tmp] += 1
    
for _l in _map:
    ans += _l * (_l - 1) / 2
    
print(int(ans))