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

from itertools import combinations

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

ans = 0

for a, b, c in combinations(L, 3):
    if a >= b + c:
        continue
    elif b >= a + c:
        continue
    elif c >= a + b:
        continue
    else:
        ans += 1
    
print(ans)

### FIXED CODE ###

from itertools import combinations
from collections import defaultdict

N = int(input())
L = list(map(int, input().split()))
L_ = sorted(L)
d = defaultdict(int)

for l in L_:
    d[l] += 1

n = 0
for i in range(2001):
    n += d[i]
    d[i] += n - d[i]

ans = 0

for a, b in combinations(L_, 2):
    #print(a, b, d[a+b-1], d[abs(a-b)], d[a+b-1] - d[abs(a-b)])
    n =  d[a+b-1] - d[abs(a-b)]
    if abs(a-b) < a:
        ans -= 1
    if abs(a-b) < b:
        ans -= 1
    ans += n
    
print(ans//3)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]

def calc_idx(x, y):
    if x > y:
        x, y = y, x
    return x + y*(y-1)//2

# create graphs & calc indegree
n_game = n * (n-1) // 2
edge = [[] for i in range(n_game)]
indegree = [0] * n_game
for i in range(n):
    for j in range(1, n-1):
        g1 = calc_idx(i, a[i][j-1])
        g2 = calc_idx(i, a[i][j])
        edge[g1].append(g2)
        indegree[g2] += 1


ans = 0
cand = [[i for i in range(n_game) if indegree[i] == 0], []]
cand = deque([(i, 1) for i in range(n_game) if indegree[i] == 0])
n_ts = 0
while cand:
    u, day = cand.popleft()
    ans = max(ans, day)
    n_ts += 1
    for v in edge[u]:
        indegree[v] -= 1
        if indegree[v] == 0:
            cand.append((v, day+1))

if n_ts != n_game:
    ans = -1

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]

def calc_idx(x, y):
    if x > y:
        x, y = y, x
    return x + y*(y-1)//2

n_game = n * (n-1) // 2
edge = [[] for i in range(n_game)]
for i in range(n):
    for j in range(1, n-1):
        g1 = calc_idx(i, a[i][j-1])
        g2 = calc_idx(i, a[i][j])
        edge[g1].append(g2)

indegree = [0] * n_game
for i in range(n_game):
    for v in edge[i]:
        indegree[v] += 1

ans = 0
cand = [i for i in range(n_game) if indegree[i] == 0]
ts = []
while cand:
    ts.extend(cand)
    cand2 = []
    for ci in cand:
        for v in edge[ci]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand2.append(v)
    cand = cand2
    ans += 1

if len(ts) != n_game:
    ans = -1

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

import math 
from itertools import product
from functools import reduce
def gcd(*numbers):
  return reduce(math.gcd,numbers)
K=int(input())
A=[]
a_s=range(1,K+1)
b_s=range(1,K+1)
c_s=range(1,K+1)
for a,b,c in product(a_s,b_s,c_s):
  s=gcd(a,b,c)
  A.append(s)
print(sum(A))

### FIXED CODE ###

import math
K=int(input())
ans=0
for a in range(1,K+1):
  for b in range(1,K+1):
    ans_=math.gcd(a,b)
    for c in range(1,K+1):
      ans+=math.gcd(ans_,c)
print(ans)
### BUGGY CODE ###

n,k,q=map(int,input().split());a={i+1:k for i in range(n)}
for _ in range(q):
  m=int(input())
  for i in range(1,n+1):
    if i==m: continue
    a[i]-=1
print(*['Yes' if a[i]>0 else 'No' for i in range(1,n+1)],sep='\n')

### FIXED CODE ###

n,k,q=map(int,input().split());a=[k-q for i in range(n)]
for _ in range(q): a[int(input())-1]+=1
print(*['Yes' if i>0 else 'No' for i in a],sep='\n')
### BUGGY CODE ###

K, A, B = map(int, input().split())
if A >= B-2:
    print(K+1)
else:
    nowb = 1
    nowm = 0
    for i in range(K):
        if nowm == 1:
            nowb += B
            nowm -= 1
        elif nowb >= A and i < K-1:
            nowb -= A
            nowm += 1
        else:
            nowb += 1
    print(nowb)

### FIXED CODE ###

K, A, B = map(int, input().split())
if A >= B-2:
    print(K+1)
else:
    nokoriK = K + 1 - A
    if nokoriK % 2 == 0:
        maisu = A + (B-A) * nokoriK // 2
    else:
        maisu = A + (B-A) * (nokoriK-1) // 2 + 1
    print(maisu)
### BUGGY CODE ###

H, n = map(int, input().split())
A = []
B = []
for i in range(n):
	a, b = map(int, input().split())
	A.append(a)
	B.append(b)

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

for i in range(1, H+1):
	dp[i] = min(dp[i - A[j]] + B[j]  if A[j] <= i  else  B[j]  for j in range(n))

print(dp[H])


### FIXED CODE ###

H, n = map(int, input().split())
A = []
B = []
for i in range(n):
	a, b = map(int, input().split())
	A.append(a)
	B.append(b)

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

for i in range(1, H+1):
	dp[i] = min(dp[i - A[j]] + B[j]  if A[j] <= i  else  B[j]  for j in range(n))

print(dp[H])
### BUGGY CODE ###

import numpy as np

n, W = list(map(int,input().split()))
w_v = [list(map(int,input().split())) for i in range(n)]
w = [w_v[i][0] for i in range(n)]
v = [w_v[i][1] for i in range(n)]
inf = 10**9+1
dp = [[inf] * (sum(v)+1) for i in range(n+1)]
#dp = np.zeros((n+1,sum(v)+1),dtype=np.int32)
dp[0][0] = 0

for i in range(n):
  for j in range(sum(v)+1):
    if j - v[i] >= 0:
      dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i])

    dp[i+1][j] = min(dp[i+1][j], dp[i][j])


for i in range(sum(v)+1):
  if dp[n][i] > W:
    pass
  else:
    ans = i
print(ans)


### FIXED CODE ###

n, W = list(map(int,input().split()))
w_v = [list(map(int,input().split())) for i in range(n)]
w = [w_v[i][0] for i in range(n)]
v = [w_v[i][1] for i in range(n)]
inf = 10**9+1
dp = [[inf] * (sum(v)+1) for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
  for j in range(sum(v)+1):
    if j - v[i] >= 0:
      dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i])

    dp[i+1][j] = min(dp[i+1][j], dp[i][j])


for i in range(sum(v)+1):
  if dp[n][i] > W:
    pass
  else:
    ans = i
print(ans)
### BUGGY CODE ###


def resolve():
    s=input()
    cnt=0
    while s.count('BW')>=1:
        s=list(s)
        for i in range(len(s)-1):
            if s[i]=='B' and s[i+1]=='W':
                cnt+=1
                s[i],s[i+1]='W','B'
        s=''.join(s)
    print(cnt)

resolve()

### FIXED CODE ###



def resolve():
    s=list(input())
    ans=[]
    cnt=0
    for i in s:
        if i=='B':
            cnt+=1
        else:
            ans.append(cnt)
    print(sum(ans))
resolve()
### BUGGY CODE ###

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

for _ in range(Q):
    A = list(input().split())
    if A[0] == "1":
        S = S[::-1]
    elif A[1] == "2":
        S = S + A[2]
    else:
        S = A[2] + S

print(S)

### FIXED CODE ###

from collections import deque

S = str(input())
Q = int(input())
t = 0

d = deque()
d.append(S)

for _ in range(Q):
    A = list(input().split())
    if A[0] == "1":
        if t == 0:
            t = 1
        else:
            t = 0

    elif (A[1] == "1" and t == 0) or (A[1] == "2" and t == 1):
        d.appendleft(A[2])
    else:
        d.append(A[2])

l = list(d)
ans = "".join(l)
if t == 1:
    ans = ans[::-1]
print(ans)
### BUGGY CODE ###

# B - Multiplication 2

n = int(input())
a = list(map(int, input().split()))
limit = 10 ** 18
for i in range(1, n):
    a[i] *= a[i - 1]
    if a[i] > limit:
        a[i] = -1
print(a[-1])


### FIXED CODE ###

# B - Multiplication 2

n = int(input())
a = list(map(int, input().split()))
limit = 10 ** 18
for i in range(1, n):
    a[i] = min(a[i] * a[i - 1], limit + 1)

print(a[-1] if a[-1] <= limit else -1)
### BUGGY CODE ###

import numpy as np
N = int(input())
S = input()
ansset = set()
counts = np.zeros((N+1, 10))
for i in range(N):
    for j in range(10):
        counts[i+1, j] = counts[i, j] + (j == int(S[i]))
for i in range(1, N-1):
    for j in range(10):
        if counts[i, j] == 0:
            continue

        for k in range(10):
            if counts[N, k] - counts[i+1, k] == 0:
                continue

            ansset.add(100*j + 10*int(S[i]) + k)

print(len(ansset))


### FIXED CODE ###

def ok(target, S):
    for t in target:
        if t in S:
            S = S[S.index(t)+1:]
        else:
            return False
    return True


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

for i in range(0, 999+1):
    target = str(i).zfill(3)
    ans += ok(target, S)

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

s = input()
q = int(input())

for _ in range(q):
    query = input()
    if query == "1":
        s = s[::-1]
    else:
        _, f, c = query.split(" ")
        s = c + s if f == "1" else s + c

print(s)


### FIXED CODE ###

s = input()
q = int(input())
rev = False
L = ""
R = ""
for _ in range(q):
    query = input()
    if query == "1":
        rev = not rev
    else:
        _, f, c = query.split(" ")
        if f == "1":
            if rev:
                R = R + c
            else:
                L = c + L
        else:
            if rev:
                L = c + L
            else:
                R = R + c

if rev:
    s = s[::-1]
    L = L[::-1]
    R = R[::-1]
    print(R + s + L)
else:
    print(L + s + R)
### BUGGY CODE ###

N,K = map(int, input().split())
P = list(map(int, input().split()))
L = []
for i in P:
    if i % 2 == 0:
        L.append((i+1)*(i//2)*(1/i))
    else:
        L.append(((i+1)*(i//2)+(i//2+1))*(1/i))
S = [0]
for i in range(N):
    S.append(sum(L[0:i+1]))
n = 0
for i in range(N-K+1):
    n = max(n,S[i+K]-S[i])
print(n)

### FIXED CODE ###

N,K = map(int, input().split())
P = list(map(int, input().split()))
L = []
S = [0]
for i in range(N):
    if P[i] % 2 == 0:
        L.append((P[i]+1)*(P[i]//2)*(1/P[i]))
    else:
        L.append(((P[i]+1)*(P[i]//2)+(P[i]//2+1))*(1/P[i]))
    S.append(L[-1]+S[-1])
n = 0
for i in range(N-K+1):
    n = max(n,S[i+K]-S[i])
print(n)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
A = sorted(a)
l = []

for i in range(1,n+1):
  z = a.index(i)
  l.append(A[z])
  
print(*l)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
List = [0]*N
 
 
for i, a in enumerate(A):
  List[int(a)-1] = str(i+1)
 
  
print(" ".join(List))
### BUGGY CODE ###

import sys

s = sys.stdin.readline().rstrip()
q = int(input())
cnt = 0
for i in range(q):
    query = input().split()
    if len(query) == 1:
        cnt += 1
    else:
        if (int(query[1]) + cnt%2)%2 == 1:
            s = "".join([query[2], s])
        else:
            s = "".join([s, query[2]])

if cnt % 2:
    s = s[::-1]
print(s)

### FIXED CODE ###

import sys
from collections import deque

s = deque([sys.stdin.readline().rstrip()])
q = int(input())
cnt = 0
for i in range(q):
    query = sys.stdin.readline().split()
    if query[0] == '1':
        cnt = (cnt + 1)%2
    else:
        if (int(query[1]) + cnt)%2 == 1:
            s.appendleft(query[2])
        else:
            s.append(query[2])
s = "".join(s)
if cnt:
    s = s[::-1]
print(s)
### BUGGY CODE ###

import sys


def solve():
    MOD = 998244353
    N, *d_l = map(int, open(0).read().split())
    ans = 1
    
    if d_l[0] != 0:
        print(0)
        sys.exit()
    
    d_max = max(d_l)
    count_l = [d_l.count(1)]
    for i in range(2, d_max+1):
        count_l.append(d_l.count(i))
    
    for i in range(1, d_max):
        ans = ans * count_l[i-1] ** count_l[i]
    
    print(ans%MOD)


if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
import collections


def solve():
    MOD = 998244353
    N, *d_l = map(int, open(0).read().split())
    ans = 1
    
    if d_l[0] != 0:
        print(0)
        sys.exit()
    
    d_max = max(d_l)
    count_dic = collections.Counter(d_l)
    if count_dic[0] != 1:
        print(0)
        sys.exit()
    
    for i in range(2, d_max+1):
        ans *= count_dic[i-1] ** count_dic[i]
    
    print(ans%MOD)


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

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

### FIXED CODE ###

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

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

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

from sys import stdin

K, S = [int(x) for x in stdin.readline().rstrip().split()]

count = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                count += 1
print(count)

### FIXED CODE ###

from sys import stdin

K, S = [int(x) for x in stdin.readline().rstrip().split()]

count = 0

for x in range(K+1):
    for y in range(K+1):
        if (x + y >= S - K) and (x + y <= S):
            count += 1
print(count)
### BUGGY CODE ###

K = int(input())
import sys
sys.setrecursionlimit(1000000)
run = [1, 2, 3, 4, 5, 6, 7, 8, 9]


def runrun(number):
    if len(number) < 16:
        last = int(number[-1])
        if last == 0:
            run.append(int(str(int(number[-1])+0)))
            run.append(int(str(int(number[-1])+1)))
            runrun(str(int(number[-1])+0))
            runrun(str(int(number[-1])+1))
        elif last == 9:
            run.append(int(str(int(number[-1])+0)))
            run.append(int(str(int(number[-1])-1)))
            runrun(str(int(number[-1])+0))
            runrun(str(int(number[-1])-1))
        else:
            run.append(int(str(int(number[-1])+0)))
            run.append(int(str(int(number[-1])-1)))
            run.append(int(str(int(number[-1])+1)))
            runrun(str(int(number[-1])+0))
            runrun(str(int(number[-1])+1))
            runrun(str(int(number[-1])-1))


for i in range(1, 10):
    runrun(str(i))
run.sort(reverse=False)
# print(len(run))
# print(run[:20])
print(run[K-1])

### FIXED CODE ###

from collections import deque
K = int(input())
que = deque(list(range(1, 10)))
for i in range(K):
    x = que.popleft()
    last = x % 10
    if last != 0:
        que.append(x*10 + last-1)
    que.append(x*10 + last)
    if last != 9:
        que.append(x*10 + last+1)
print(x)
### BUGGY CODE ###

# damedatta
def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l
def main():
    X, Y, Z, K = map(int, input().split())
    A = sorted(map(int, input().split()), reverse=True)
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    D = sorted((i + j for i in B for j in C), reverse=True)
    def calc(x):
        t = 0
        ii = len(D) - 1
        for i in A:
            while ii >= 0 and D[ii] + i < x:
                ii -= 1
            t += ii + 1
            if t >= K:
                return True
            else:
                return False
    l = binsearch(D[-1] + A[-1], D[0] + A[0], calc)
    ii = len(D) - 1
    rl = []
    for i in A:
        while ii >= 0 and D[ii] + i < l:
            ii -= 1
        if ii < 0:
            break
        rl.extend([i + j for j in D[:ii+1]])
    rl.sort(reverse=True)
    print('\n'.join(str(i) for i in rl[:K]))
main()


### FIXED CODE ###

# damedatta
def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l
def main():
    X, Y, Z, K = map(int, input().split())
    D = sorted(map(int, input().split()), reverse=True)
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    A = sorted((i + j for i in B for j in C), reverse=True)
    def calc(x):
        t = 0
        ii = len(D) - 1
        for i in A:
            while ii >= 0 and D[ii] + i < x:
                ii -= 1
            t += ii + 1
            if t >= K:
                return True
            if ii < 0:
                return False
        return t >= K
    l = binsearch(D[-1] + A[-1], D[0] + A[0]+1, calc)
    ii = len(D) - 1
    rl = []
    for i in A:
        while ii >= 0 and D[ii] + i < l + 1:
            ii -= 1
        if ii < 0:
            break
        rl.extend(i + j for j in D[:ii+1])
    rl.sort(reverse=True)
    rl += [l] * (K - len(rl))
    print('\n'.join(str(i) for i in rl))
main()
### BUGGY CODE ###

N,*A=map(int,open(0))
x=0
B=[]
for a in A:
	x^=a
	B+=a^a-1,
z=0
k=2**30
for b in sorted(set(B))[::-1]:
	while not(x&k):
		k//=2
	if b&k:
		x^=b
		z+=1
print(-1if x else z)

### FIXED CODE ###

N,*A=map(int,open(0))
x=0
B=[]
for a in A:
	x^=a
	B+=a^a-1,
z=0
k=2**30
for b in sorted(B)[::-1]:
	while k and not(x&k):
		k//=2
	if b&k and b<2*k:
		x^=b
		z+=1
print(-1if x else z)
### BUGGY CODE ###

import re
s = str(input())
cnt=0
while len(s) >1:
    if '10' in s:
        cnt+=2 * s.count('10')
        s=re.sub('10', '',s) 
        cnt+=2 * s.count('01')
        s=re.sub('01', '',s) 
        
    elif '01' in s:
        cnt+=2 * s.count('01')
        s=re.sub('01', '',s) 
        
        cnt+=2 * s.count('10')
        s=re.sub('10', '',s) 
    else:
        break
print(cnt)

### FIXED CODE ###

#120 C
S =input()
print(min(S.count('0'),S.count('1'))*2)
### BUGGY CODE ###

from collections import deque
import copy

def main():
    H, W = map(int,input().split())

    A = [[s == "#" for s in input()] for _ in range(H)]
    Q = deque([(y, x) for y in range(H) for x in range(W) if A[y][x]])

    ans = 0
    while True:
        ans += 1
        NQ = deque()
        while Q:
            y, x = Q.popleft()
            if x > 0 and A[y][x-1] == False:
                A[y][x-1] = True
                NQ.append((y,x-1))
            if x < W-1 and A[y][x+1] == False:
                A[y][x+1] = True
                NQ.append((y,x+1))
            if y > 0 and A[y-1][x] == False:
                A[y-1][x] = True
                NQ.append((y-1, x))
            if y < H-1 and A[y+1][x] == False:
                A[y+1][x] = True
                NQ.append((y+1,x))
        if NQ:
            Q = copy.copy(NQ)
        else:
            break

    print(ans-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    H, W = map(int,input().split())

    A = [[False for _ in range(W)] for _ in range(H)]

    Q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "#":
                Q.append((y, x))
                A[y][x] = True

    ans = 0
    while Q:
        ans += 1
        NQ = []
        for y, x in Q:
            if x > 0 and A[y][x-1] == False:
                A[y][x-1] = True
                NQ.append((y,x-1))
            if x < W-1 and A[y][x+1] == False:
                A[y][x+1] = True
                NQ.append((y,x+1))
            if y > 0 and A[y-1][x] == False:
                A[y-1][x] = True
                NQ.append((y-1, x))
            if y < H-1 and A[y+1][x] == False:
                A[y+1][x] = True
                NQ.append((y+1,x))
        if NQ:
            Q = NQ
        else:
            break

    print(ans-1)

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

def match(S,pat):
    i = 0
    for s in S:
        if s == pat[i]:
            i += 1
        if i == 3:
            return True
    return False

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

for n in range(1000):
    s = str(n)
    if len(s) == 1:
        s = '00'+s
    elif len(s) == 2:
        s = '0'+s
    else:
        pass
    if  match(S,s):
        ans += 1
    
print(ans)

### FIXED CODE ###

def match(S,pat):
    i = 0
    for s in S:
        if s == pat[i]:
            i += 1
        if i == 3:
            return True
    return False

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

for n in range(1000):
    s = str(n)
    if len(s) == 1:
        s = '00'+s
    elif len(s) == 2:
        s = '0'+s
    else:
        pass
    if  match(S,s):
        ans += 1
    
print(ans)
### BUGGY CODE ###

S=input()
T=input()
d=[[] for i in range(26)]
for i,c in enumerate(S):
    d[ord(c)-ord('a')].append(i)
d2=[[] for i in range(26)]
for i,c in enumerate(T):
    d2[ord(c)-ord('a')].append(i)
d.sort()
d2.sort()
f=1
for i in range(26):
    if len(d[i])!=len(d2[i]):
        f=0
    else:
        for j in range(len(d[i])):
            if d[i]!=d2[i]:
                f=0
print(['No','Yes'][f])

### FIXED CODE ###

S=input()
T=input()
d=[[] for i in range(26)]
for i,c in enumerate(S):
    d[ord(c)-ord('a')].append(i)
d2=[[]for i in range(26)]
for i,c in enumerate(T):
    d2[ord(c)-ord('a')].append(i)
print(['No','Yes'][set((tuple(x) for x in d))==set((tuple(x) for x in d2))])
### BUGGY CODE ###

import sys
import queue
s = list(map(str,input()))
t = list(map(str,input()))

if len(set(s) & set(t)) < len(set(t)):
    print(-1)
    sys.exit()

q = queue.Queue()
for i in range(len(s)):
    q.put(s[i])
w = t[::-1]

ans = 0
while len(w) > 0:
    a = q.get()
    b = w[len(w)-1]
    if a == b:
        w.pop()
    q.put(a)
    ans += 1
print(ans)

### FIXED CODE ###

from bisect import bisect_right, bisect_left
s = [ord(i) - ord("a") for i in input()]
t = [ord(i) - ord("a") for i in input()]
index = [[] for _ in range(26)]

for i, x in enumerate(s):
    index[x].append(i)


l_s = len(s)

for x in index:
    if x:
        x.append(x[0] + l_s)

cnt = -1
for r in t:
    seq = index[r]
    if not seq:
        cnt = -2
        break
    i = cnt % l_s
    j = bisect_right(seq, i)
    cnt += seq[j] - i

print(cnt+1)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
from collections import Counter
n=int(input())
A=tuple(input().split())
C=Counter(A)
c1,c2,c3=[C[s] for s in ('1','2','3')]
DP=[[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)] 
DP[0][0][0]=0
for i in range(c3+1):
    for j in range(c3+c2-i+1):
        for k in range(n-i-j+1):
            if i==j==k==0:
                continue
            tmp=n
            if i>0:
                tmp+=DP[k][j+1][i-1]*i
            if j>0:
                tmp+=DP[k+1][j-1][i]*j
            if k>0:
                tmp+=DP[k-1][j][i]*k
            DP[k][j][i]=tmp/(i+j+k)
print(DP[c1][c2][c3])

### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import Counter
n=int(input())
A=tuple(input().split())
C=Counter(A)
c1,c2,c3=[C[s] for s in ('1','2','3')]
DP=[[[0.0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
for i in range(c3+1):
    for j in range(c3+c2-i+1):
        for k in range(n-i-j+1):
            if i==j==k==0:
                continue
            tmp=n
            if i>0:
                tmp+=DP[k][j+1][i-1]*i
            if j>0:
                tmp+=DP[k+1][j-1][i]*j
            if k>0:
                tmp+=DP[k-1][j][i]*k
            DP[k][j][i]=tmp/(i+j+k)
print(DP[c1][c2][c3])
### BUGGY CODE ###

import heapq
import sys
N,M=map(int,input().split())
A=sorted(list(map(int,input().split())))
lst=[[0,0] for _ in range(M)]
h=[]
for i in range(M):
  lst[i]=list(map(int,input().split()))
  heapq.heappush(h,[-1*lst[i][1],lst[i][0]])

for i in range(M):
  v=heapq.heappop(h)
  v1,v2=-1*v[0],v[1]
  if A[0]>v1:
    print(sum(A))
    sys.exit()
  else:
    while v2!=0 and A[0]<v1:
      val=A.pop(0)
      heapq.heappush(A,v1)
      v2-=1 
print(sum(A))

### FIXED CODE ###

import heapq
import sys
N,M=map(int,input().split())
A=sorted(list(map(int,input().split())))
lst=[[0,0] for _ in range(M)]
h=[]
for i in range(M):
  lst[i]=list(map(int,input().split()))
  heapq.heappush(h,[-1*lst[i][1],lst[i][0]])
i=0
while len(h)!=0:
    v=heapq.heappop(h)
    v1,v2=-1*v[0],v[1]
    while i<=N-1 and A[i]<v1 and v2!=0:
        A[i]=v1
        i+=1
        v2-=1
    if v2>=1:
        print(sum(A))
        sys.exit()
print(sum(A))
### BUGGY CODE ###

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


### FIXED CODE ###

s = input()
ans = 0
tmp = 0
mods = [0]*2019
mods[0] = 1
order = 1
for i in reversed(s):
    tmp += int(i) * order
    mods[tmp % 2019] += 1
    order *= 10
    order %= 2019
ans = sum(n*(n-1)//2 for n in mods)
print(int(ans))