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

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

L.sort()
cnt=0
for i in range(n-2):
    for j in range(i+1,n-1):
        if L[i]+L[j]<=L[j+1]:
            continue
        if L[i]+L[j]>L[n-1]:
            cnt+=n-j-1
            continue
        left=j+1
        right=n-1
        while right-left>1:
            mid=left+(right-left)//2
            if L[mid]<L[i]+L[j]:
                left=mid
            else:
                right=mid
        cnt+=left-j
print(cnt)

### FIXED CODE ###

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

L.sort()
cnt=0
for i in range(n-2):
    for j in range(i+1,n-1):
        if L[i]+L[j]<=L[j+1]:
            continue
        if L[i]+L[j]>L[n-1]:
            cnt+=n-j-1
            continue
        left=j+1
        right=n-1
        while right-left>1:
            mid=left+(right-left)//2
            if L[mid]<L[i]+L[j]:
                left=mid
            else:
                right=mid
        cnt+=left-j
print(cnt)
### BUGGY CODE ###

import sys
import random

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def query(i):
    print(i)
    sys.stdout.flush()
    s = in_s()
    if s == 'Vacant':
        exit(0)
    elif s == 'Male':
        return 0
    elif s == 'Female':
        return 1


def main():

    N = in_n()

    min_i = 0
    max_i = N

    fm = query(0)

    while max_i - min_i != 1:
        now_i = (min_i + max_i) // 2
        now_fm = query(now_i)

        if (now_i - min_i) % 2 == 0:
            if now_fm == fm:
                min_i = now_i
            else:
                max_i = now_i
        elif (now_i - min_i) % 2 == 1:
            if now_fm == fm:
                max_i = now_i
            else:
                min_i = now_i

        fm = now_fm


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import random

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def query(i):
    print(i)
    sys.stdout.flush()
    s = in_s()

    if s == 'Vacant':
        exit(0)
    elif s == 'Male':
        return 0
    elif s == 'Female':
        return 1


def main():

    N = in_n()

    min_i = 0
    max_i = N

    min_fm = query(0)
    max_fm = min_fm

    while max_i - min_i != 1:
        now_i = (min_i + max_i) // 2
        now_fm = query(now_i)

        if abs(now_i - min_i) % 2 == 0 and now_fm != min_fm:
            max_i = now_i
            max_fm = now_fm
        elif abs(now_i - min_i) % 2 == 1 and now_fm == min_fm:
            max_i = now_i
            max_fm = now_fm
        elif abs(now_i - max_i) % 2 == 0 and now_fm != max_fm:
            min_i = now_i
            min_fm = now_fm
        elif abs(now_i - max_i) % 2 == 1 and now_fm == max_fm:
            min_i = now_i
            min_fm = now_fm


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

r,g,b,n = map(int, input().split())
res = 0
for i in range(n+1):
    for j in range(n+1):
        if r*i + g*j <= n:
            if (n-(r*i + g*j)) % b==0:
                res += 1           
print(res)

### FIXED CODE ###

def main():
    r,g,b,n = map(int, input().split())
    tmp = [r,g,b]
    r,g,b = sorted(tmp, reverse=True)
    res = 0
    for i in range(n//r + 1):
        if i*r > n:
            break
        for j in range(n//g + 1):
            if r*i + g*j > n:
                break
            if (n-(r*i + g*j)) % b==0:
                res += 1           
    print(res)

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

N = int(input())
A = list(map(int, input().split()))
l = []
for i in A:
    if i in l:
        print("NO")
        exit()
    l.append(i)
print("YES")

### FIXED CODE ###

N = int(input())
A = set(map(int, input().split()))
print("YES" if len(A) == N else "NO")
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def is_ok(a, key, idx):
    if a[idx] >= key:
        return True
    else:
        return False


def binary_search(a, key):
    """Meguru type binary search"""
    ng = -1
    ok = len(a)

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(a, key, mid):
            ok = mid
        else:
            ng = mid

    return ok


def solve(N, L):
    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            c = binary_search(L, L[a] + L[b]) - 1
            ans += c - b
    return ans


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

    ans = solve(N, L)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from bisect import bisect_left

input = sys.stdin.readline


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

    L.sort()
    ans = 0
    for i in range(N - 1):
        a = L[i]
        for j in range(i + 1, N):
            k = bisect_left(L, a + L[j])
            ans += (k - 1 - j)

    print(ans)


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

import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


fact = [1] * 200100
for i in range(1, 200100):
    fact[i] = fact[i-1] * i % MOD


def calc(h, w):
    h -= 1
    w -= 1
    return (fact[h+w]*modinv(fact[h]) % MOD)*modinv(fact[w]) % MOD


h, w, a, b = map(int, input().split())
ans = 0
for i in range(1, h - a + 1):
    ans += calc(i, b) * calc(h + 1 - i, w - b) % MOD
    if ans >= MOD:
        ans -= MOD
print(ans)


### FIXED CODE ###

import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


fact = [1] * 200100
for i in range(1, 200100):
    fact[i] = fact[i-1] * i % MOD


def calc(h, w):
    h -= 1
    w -= 1
    return (fact[h+w]*modinv(fact[h]) % MOD)*modinv(fact[w]) % MOD


h, w, a, b = map(int, input().split())
if a >= h // 2:
    ans = 0
    for i in range(1, h - a + 1):
        ans += calc(i, b) * calc(h + 1 - i, w - b) % MOD
        if ans >= MOD:
            ans -= MOD
    print(ans)

else:
    ans = calc(h, w)
    for i in range(h-a+1, h + 1):
        ans -= calc(i, b) * calc(h + 1 - i, w - b) % MOD
        if ans < 0:
            ans += MOD
    print(ans)
### BUGGY CODE ###

#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

q=int(input())
lr=[[int(x) for x in input().split()] for _ in range(q)]

max_n=max(sum(lr,[]))
primelist=primes(max_n)
for query in lr:
  res=0
  for item in range(query[0],query[1]+1,2):
    if (item in primelist) and ((item+1)/2 in primelist):
      res+=1
  print(res)

### FIXED CODE ###

import numpy as np

#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

q=int(input())
lr=[[int(x) for x in input().split()] for _ in range(q)]

primelist=[0,]*(100000+1)
for n in primes(100000):
  primelist[n]=1

list2017=[primelist[n] and primelist[(n+1)//2] for n in range(1,100000,2)]
cumsum=np.cumsum(list2017)
for query in lr:
  print(cumsum[(query[1]-1)/2]-cumsum[max(0,(query[0]-1)/2-1)])
### BUGGY CODE ###

from collections import deque
N=int(input())
S=input()
w=[0]
e=[0]
a=0
b=0
c=N
de=deque(e)
for i in range(len(S)-1):
    if S[i]=="W":
        a+=1   
    w.append(a)
    if S[-(i+1)]=="E":
        b+=1
    de.appendleft(b)
for i in range(N):
    if w[i]+de[i]<c:
        c=w[i]+de[i]
print(c)

### FIXED CODE ###

from collections import deque
N=int(input())
S=input()
w=[0]
e=[0]
a=0
b=0
c=N
for i in range(len(S)-1):
    if S[i]=="W":
        a+=1   
    w.append(a)
    if S[-(i+1)]=="E":
        b+=1
    e.append(b)
for i in range(N):
    d=w[i]+e[-(i+1)]
    if d<c:
        c=d
print(c)
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
for i in range(N):
    print(A.count(i+1))

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
lst=[0]*N
for a in A:
    lst[a-1]+=1
for l in lst:
    print(l)
### BUGGY CODE ###

from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[[] for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
g=[[ 0 for _ in range(N)] for _ in range(N)]

for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
f=deepcopy(d)
#print(f)

#x=0としてBFSする
v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  maxi=max(maxi,len(d[k]))
  all=set(i+1 for i in range(len(d[k])))
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      s=min(pos)
      c[k].add(s)
      c[item].add(s)
      pos.remove(s)
      e[item] = e[k]+1
      v.append(item)
      g[k][item]=s
      g[item][k]=s
      
print(maxi)
for i in range(N-1):
  print( g[a[i]-1][b[i]-1] )

### FIXED CODE ###

from collections import deque

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)] # 使用している色
d=[set() for _ in range(N)] # 隣接リスト
e=[ False for _ in range(N)] #訪問ずみかどうか
f=[0]*N  #答え
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)

maxi=max([len(d[i]) for i in range(N-1)])
print(maxi)
#print("c:",c)
#print("d",d)
#print("e",e)

#x=0としてBFSする

v=deque([0])
e[0]=True
color=1

while v:
  p = v.popleft()
  for q in d[p]:
    if e[q]==False:
      while color in c[p]:
        color +=1
        if color>maxi:
          color=1
      c[p].add(color)
      c[q].add(color)
      f[q]=color
      e[q]=True
      v.append(q)
      
for i in range(N-1):
  print( f[b[i]-1])
### BUGGY CODE ###

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

cums = [0]
for a in A:
    cums.append(cums[-1] + a)

ans = 0
for d in range(1,K):
    for i in range(N+1-d):
        v = (cums[i+d] - cums[i]) % K
        if v==d:
            ans += 1
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
B = [a%K for a in A]
cs = [0]
for b in B:
    c = (cs[-1] + b-1) % K
    cs.append(c)

from collections import deque
from collections import defaultdict
qs = defaultdict(lambda: deque())

ans = 0
for i,c in enumerate(cs):
    while qs[c] and qs[c][0] + K <= i:
        qs[c].popleft()
    ans += len(qs[c])
    qs[c].append(i)
print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

dp = Counter()

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

geta = 1000
geta2 = geta**2
CA = Counter(A)
SA = CA[1]
SB = CA[2]
SC = CA[3]
for c in range(SC+1):
    for b in range(SB+SC+1):
        if b + c > N:
            break
        for a in range(N+1):
            if a + b + c > N:
                break
            S = a + b + c
            if S == 0:
                continue
            dp[a*geta2 + b*geta + c] = N/S + a/S*dp[(a-1)*geta2 + b*geta + c]\
            +b/S*dp[(a+1)*geta2 + (b-1)*geta + c]\
            +c/S*dp[a*geta2 + (b+1)*geta + c - 1]

print(dp[SA*geta2 + SB*geta + SC])

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

dp = [[[0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
CA = Counter(A)
SA = CA[1]
SB = CA[2]
SC = CA[3]
for c in range(SC+1):
    for b in range(SB+SC+1):
        if b + c > N:
            break
        for a in range(N+1):
            if a + b + c > N:
                break
            S = a + b + c
            if S == 0:
                continue
            dp[a][b][c] = N/S + a/S*dp[a-1][b][c]\
            +b/S*dp[a+1][b-1][c]\
            +c/S*dp[a][b+1][c - 1]

print(dp[SA][SB][SC])
### BUGGY CODE ###

N=int(input())
B=[]

for i in range(N):
    a=int(input())
    if a in B:
        B.remove(a)
    else:
        B.append(a)
print(len(B))

### FIXED CODE ###

N=int(input())
B=set()

for i in range(N):
    a=int(input())
    if a in B:
        B.remove(a)
    else:
        B.add(a)
print(len(B))
### BUGGY CODE ###

import numpy as np
n, W = list(map(int, input().split()))
w = [0 for i in range(n + 1)]
v = [0 for i in range(n + 1)]
for i in range(n):
    w[i + 1], v[i + 1] = list(map(int, input().split()))
dp = np.zeros((n + 1,W+1))
for i in range(1,n+1):
    for j in range(1,W+1):
        if w[i] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
print(int(dp[n][W]))

### FIXED CODE ###

n, W = list(map(int, input().split()))
w = [0 for i in range(n + 1)]
v = [0 for i in range(n + 1)]
for i in range(n):
    w[i + 1], v[i + 1] = list(map(int, input().split()))
dp = [[0 for i in range(W+1)] for j in range(n+1)]
for i in range(1,n+1):
    for j in range(1,W+1):
        if w[i] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
print(int(dp[n][W]))
### BUGGY CODE ###

N=int(input())
A=input().split()
A=[int(i) for i in A]
S=0
A_sum=[]
for i in range(N):
    sum=0
    for j in range(i+1,N):
        sum+=A[j]
    A_sum.append(sum)
    


for i in range(N-1):
    S+=A[i]*A_sum[i]

print(S%(pow(10,9)+7))

### FIXED CODE ###

N=int(input())
A=input().split()
A=[int(i) for i in A]
S=0
A_sum=0
for i in range(N):
    A_sum+=A[i]
    

B=A_sum
for i in range(N):
    B-=A[i]
    S+=A[i]*B

print(S%(pow(10,9)+7))
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
use=1 
for i in range(n):
    use*=A[i]

print(use if use<=10**18 else -1)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
want=A.count(0)
if want:
    print(0)
    exit()
use=1 
for i in range(n):
    use*=A[i]
    if use>10**18:
        print(-1)
        exit()

print(use)
### BUGGY CODE ###

import bisect
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, P_id[N], N] 


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    if l1 != - 1:
        l2 = A[j - 2]
    else:
        l2 = l1
    if r1 != N:
        r2 = A[j + 2]
    else:
        r2 = r1
    
    if l1 == - 1:
        res += i*(A[j] + 1)*(r2 - r1)
    elif r1 == N:
        res += i*(l1 - l2)*(N - A[j])
    else:
        res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))
print(res)

### FIXED CODE ###

import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)
### BUGGY CODE ###

import itertools
N, K = map(int, input().split())
p = list(map(int, input().split()))

c = itertools.combinations(p, K)
ans = 10**10
for i in c:
    ans = min(ans, sum(i))
print(ans)

### FIXED CODE ###

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

p.sort()
print(sum(p[:K]))
### BUGGY CODE ###

s=int(input())
mod=10**9+7


dp=[[0]*(s+1) for _ in range(s)]

for i in range(3,s+1):
    dp[0][i]=1

ans=0
ans+=dp[0][s]

for keta in range(1,s//3+1):
    #print("keta",keta)
    flag=0
    for ss in range(3*keta,s+1):
        for k in range(3,s+1):

            if ss+k<=s:
                dp[keta][ss+k]+=dp[keta-1][ss]
                dp[keta][ss+k]%=mod
            else:
                break


    ans+=dp[keta][s]
    ans%=mod

#print(dp)
    

print(ans%mod)






### FIXED CODE ###

s=int(input())
mod=10**9+7

if s<3:
    print(0)
    exit()

dp=[1]*(s+1)

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

#print(dp)
for i in range(3,s+1):
    for j in range(3,s-i+1):
        dp[i+j]+=dp[i]%mod
    #print(i,dp)
print(dp[s]%mod)
### BUGGY CODE ###

N = int(input())
abc = [chr(i) for i in range(97, 97+26)]
ss = []
ct = []
ans = 0

for i in range(N):
    s = input()
    cnt = [0]*26
    for j in s:
        cnt[abc.index(j)] += 1
    if not cnt in ss:
        ss.append(cnt)
        ct.append(1)
    else:
        ct[ss.index(cnt)] += 1

for i in range(len(ct)):
    if ct[i] > 1:
        ans += int((ct[i] * (ct[i] - 1))/2)


print(ans)


### FIXED CODE ###

N = int(input())
ss = {}
ht = []
ans = 0

for i in range(N):
    s = ''.join(sorted(input()))
    if not s in ss.keys():
        ss[s] = 1
    else:
        ans += ss[s]
        ss[s] += 1

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

#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    def chmin(idx):
        mn = INF
        for i in range(1, k+1):
            if idx - i >= 0:
                temp = abs(h[idx] - h[idx-i]) + dp[idx-i]
                if temp < mn:
                    mn = temp
        return mn

    n, k = list(map(int,ipti().split()))
    h = list(map(int,ipti().split()))
    dp = [0] * n

    for i in range(1, n):
        dp[i] = chmin(i)

    print(dp[n-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, k = list(map(int,ipti().split()))
    h = list(map(int,ipti().split()))
    dp = [INF] * n
    dp[0] = 0

    for i in range(1, n):
        for j in range(1, k+1):
            if i - j >= 0:
                temp = abs(h[i] - h[i-j]) + dp[i-j]
                dp[i] = min(dp[i], temp)

    print(dp[n-1])

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

N = int(input())
*A, = map(int, input().split())
ans = 1
for a in A: ans *= a
if ans > 10**18: ans = -1
print(ans)

### FIXED CODE ###

N = int(input())
*A, = map(int, input().split())
if 0 in A: print(0)
else:
    ans = 1
    for a in A:
        ans *= a
        if ans > 10**18: ans = -1; break
    print(ans)
### BUGGY CODE ###

import copy
n = int(input())
ls = []
for i in range(n):
    ls.append(int(input()))
for j in range(n):
    lss = copy.deepcopy(ls) 
    del lss[j]
    tmpmax = max(lss)
    print(tmpmax)

### FIXED CODE ###

import numpy as np
ls = []
n = int(input())
for i in range(n):
    ls.append(int(input()))
ls = np.array(ls)
maxindex1 = np.argmax(ls)
for j in range(n):
    if j != maxindex1:
        print(ls[maxindex1])
    else:
        tmp = ls[maxindex1]
        ls[maxindex1] = 0 
        maxindex2 = np.argmax(ls)
        print(ls[maxindex2])
        ls[maxindex1] = tmp
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    S = list(map(int, list(input())))
    S = S[::-1]
    n = len(S)
    mod = 2019

    A = [0] * n
    times = 1
    for i in range(n):
        A[i] = S[i] * times % mod
        times = times * 10

    # 累積和
    R = [0] * (n + 1)
    for i in range(n):
        R[i+1] = (R[i] + A[i]) % mod
    # print(R)
    cnt = {}
    ans = 0
    for i in range(n+1):
        r = R[i] % mod
        # print(r)
        ans = ans + cnt.get(r, 0)
        # cnt.setdefault(r, 0)
        # ans = ans + cnt[r]
        cnt[r] = cnt.get(r, 0) + 1
    # print(cnt)
    print(ans)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())
 
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
 
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
 
INF = float('inf')
 
def solve():
    S = list(map(int, list(input())))
 
    S = S[::-1]
    # print(S)
    n = len(S)
    mod = 2019
 
    #
    A = [0] * (n)
    a = 1
    for i in range(n):
        A[i] = S[i] * a
        a = a * 10 % mod
    # print(A)
 
    # 累積和
    R = [0] * (n+1)
    for j in range(n):
        R[j+1] = (R[j] + A[j]) % mod
    # print(R)
 
    # 個数を数える
    cnt = {}
    ans = 0
    for l in range(0, n+1):
        r = R[l]
        ans = ans + cnt.get(r, 0)
        cnt[r] = cnt.setdefault(r, 0) + 1
    print(ans)
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

n, k = map(int, input().split())
tmp = n
while True:
    tmp = n
    n = abs(n-k)
    if tmp<n:
        n = tmp
        break
print(n) 
    

### FIXED CODE ###

n, k = map(int, input().split())
tmp = n
n = n%k
while True:
    tmp = n
    n = abs(n-k)
    if tmp<n:
        n = tmp
        break
print(n)
### BUGGY CODE ###

N = int(input())

lst = list(map(int, input().split()))
lst1 = lst[::2]
lst2 = lst[1::2]

#print (lst, lst1, lst2)

a1 = 0
a2 = 0
b1 = 0
b2 = 0
for i in range(N//2):
    a = lst1.count(lst1[i])
    b = lst2.count(lst2[i])
    if a > a1:
        c = lst1[i]
        a1, a2 = a, a1
    elif a > a2 and lst1[i] != c:
        a2 = a
    if b > b1:
        d = lst2[i]
        b1, b2 = b, b1
    elif b > b2 and lst2[i] != d:
        b2 = b

#print(a1, a2, b1, b2)
if c == d:
    ans = max(a1+b2, a2+b1)
else:
    ans =a1 + b1

print (N - ans)

### FIXED CODE ###

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

dic1, dic2 = dict(), dict()
#dic1[0] = 0
#dic2[0] = 0
for i, x in enumerate(lst):
    dic = dic1 if  i%2 == 0 else dic2
    if x not in dic.keys():
        dic[x] = 1
    else:
        dic[x] += 1
#print (type(dic1))
dic1 =sorted(dic1.items(), key = lambda x:x[1])[::-1]
dic2 =sorted(dic2.items(), key = lambda x:x[1])[::-1]

#print (type(dic2))
#print (dic1)
#print (dic2)

if dic1[0][0] != dic2[0][0]:
    print (N-dic1[0][1]-dic2[0][1])
elif len(dic1) == 1 and len(dic2) == 1:
    print (N//2)
elif len(dic1) == 1:
    print (N-dic1[0][1]-dic2[1][1])
elif len(dic2) == 1:
    print (N-dic1[1][1]-dic2[0][1])
else:
    print (min(N-dic1[0][1]-dic2[1][1], N-dic1[1][1]-dic2[0][1]))
### BUGGY CODE ###

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

for i in range(N):
    ans = ans*A[i]
    
if ans >10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))
ans = 1
flag = 0
if(A[0] == 0):
    print(0)
else:
    for i in range(N):
        ans = ans*A[i]
        if ans >10**18:
            flag = 1
            break
    if(flag == 0):
        print(ans)
    else:
        print(-1)