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

def main():
    S = input()
    l = []
    l2 = []
    mod = (10 ** 9) + 7
    for i in range(6):
        d = [0] * 13
        d2 = [0] * 10
        for j in range(0, 10):
            t = (j *(10 ** i)) % 13
            d[t] += 1
            d2[j] = t
        l.append(d)
        l2.append(d2)
    r = 0
    c = [0] * 13
    c[0] = 1
    n = [0] * 13
    for i, v in enumerate(reversed(S)):
        if v == '?':
            for j in range(13):
                for k in range(13):
                    n[(j + k) % 13] += c[k] * l[i % 6][j]
            c = n
            n = [0] * 13
        else:
            r += (l2[i % 6][int(v)])
    r = (5 - r) % 13
    print(c[r] % mod)
main()



### FIXED CODE ###

def main():
    S = input()
    l = []
    l2 = []
    mod = (10 ** 9) + 7
    for i in range(6):
        d = [0] * 13
        d2 = [0] * 10
        for j in range(0, 10):
            t = (j *(10 ** i)) % 13
            d[t] += 1
            d2[j] = t
        l.append(d)
        l2.append(d2)
    r = 0
    c = [0] * 13
    c[0] = 1
    n = [0] * 13
    i = 0
    for v in reversed(S):
        if v == '?':
            k = 0
            for j in range(13):
                for k in range(13):
                    if l[i][j]:
                        kk = (j+k) % 13
                        n[kk] += c[k]
                        n[kk] %= mod
            c = n
            n = [0] * 13
        else:
            r += (l2[i][int(v)])
            r %= 13
        i += 1
        i %= 6
    r = (5 - r) % 13
    print(c[r] % mod)
main()
### BUGGY CODE ###

n, m = map(int, input().split(' '))
ans = []
c = 0
p = {} 
p_ = 0
for i in range(m):
  arr = list( input().split(' '))
  if ans.count(arr[0]) == 0:
    if not arr[0] in p:
      p[arr[0]] = 0
    if arr[1] == 'WA':
      p[arr[0]] += 1
      
    if arr[1] == 'AC':
      c += 1
      ans.append(arr[0])
      p_ += p[arr[0]]
      
      
print(c,p_)

### FIXED CODE ###

n, m = map(int, input().split(' '))
ans = {}

p = {} 
p_ = 0
for i in range(m):
  arr = list( input().split(' '))
  if not arr[0] in ans :
    if not arr[0] in p:
      p[arr[0]] = 0
    if arr[1] == 'WA':
      p[arr[0]] += 1
    if arr[1] == 'AC':
      ans[arr[0]] = 0
      p_ += p[arr[0]]
      p.pop(arr[0])
      
      
print(len(ans),p_)
### BUGGY CODE ###

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

ans = [0]*(N+1)

for i in range(1,N+1):
    ans[i] = A.count(i)

for j in range(1,N+1):
    print(ans[j])


### FIXED CODE ###

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

import collections
c = collections.Counter(A)

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

def main():
  s=input()
  q=int(input())
  count=0
  for _ in [0]*q:
    a=list(input().split())
    if len(a)==1:
      count+=1
    else:
      if count%2==1:
        s=s[::-1]
        count=0
      if a[1]=='1':
        s=a[2]+s
      else:
        s=s+a[2] 
  if count%2==1:
    s=s[::-1]
  print(s)
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  from collections import deque
  s=deque(input())
  q=int(input())
  count=0
  for _ in [0]*q:
    a=list(input().split())
    if len(a)==1:
      count+=1
    else:
      if count%2==0:
        if a[1]=='1':
           s.appendleft(a[2])
        else:
          s.append(a[2])
      else:
        if a[1]=='1':
          s.append(a[2])
        else:
          l=(a[2],s)
          s.appendleft(a[2])
  if count%2==1:
    s=list(s)[::-1]
  print(''.join(s))
if __name__=='__main__':
  main()
### BUGGY CODE ###

#import itertools
N = int(input())
S = input()
ans = 0
#cnt = 0

for i in range(0, N):
    for j in range(i+1, N-1):
        if S[i] == S[j]:
            continue
        for k in range(j+1, N):
            #cnt += 1
            if j - i == k - j:
                continue
            if S[i] == S[j] or S[i] == S[k] or S[j] == S[k]:
                continue
            ans += 1
            #print(f"i={i},j={j},k={k}")
#print(cnt)
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
total = S.count('R') * S.count('G') * S.count('B')
cnt = 0

for i in range(0, N-2):
    for j in range(i+1, N-1):
        if S[i] == S[j]:
            continue
        k = 2 * j - i
        if k > N - 1:
            break
        if S[i] == S[k] or S[j] == S[k]:
            continue
        cnt += 1
print(total - cnt)
### BUGGY CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
arr = [round(float(input()) * 10**9) for _ in range(n)]
arr2 = [div(x, 2) for x in arr]
arr5 = [div(x, 5) for x in arr]

ans = 0
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        if arr2[i] + arr2[j] >= 18 and arr5[i] + arr5[j] >= 18:
            ans += 1

print(ans)

### FIXED CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

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

N = int(input())

ls = [input() for i in range(N)]

ls = [sorted(list(s)) for s in ls]

hoge = 0
for _ in range(N):
    hoge += sum([1 if x==ls[0] else 0 for x in ls]) - 1
    del ls[0]

print(hoge)

### FIXED CODE ###

N = int(input())
s = [''.join(sorted(input().rstrip())) for _ in range(N)]

memo = {}
for x in s:
    if x not in memo:
        memo[x] = 1
    else:
        memo[x] += 1

print(sum(x*(x-1)//2 for x in memo.values()))
### BUGGY CODE ###

n = int(input())

cnt = 0
target = set(["3","5","7"])
for i in range(1,n+1):
  check = set(str(i))
  if (len(target.intersection(check))==3) & (len(check)==3):
    cnt+=1
print(cnt)

### FIXED CODE ###

from itertools import product
target = ['3','5','7']

n=int(input())
tmp=n
keta=0
while tmp!=0:
  tmp//=10
  keta+=1
check_list = []
for i in range(1,keta+1):
  tmp=[]
  for _ in range(i):
    tmp.append(target.copy())
    tmp_product = list(product(*tmp))
  check_list+=[int(''.join(nums)) for nums in tmp_product]
check_list = sorted(check_list)

cnt=0
for i in check_list:
  if i <= n:
    tmp = set([w for w in str(i)])
    if len(tmp)==3:
      cnt+=1
  else:
    break
print(cnt)
### BUGGY CODE ###

n = int(input())
l_s = list(map(int,input().split()))
l_s.append(0)
l_s.sort()
ans = 0
#一番長い辺を選ぶ
#print(l_s)
for j in range(2,n):
    for i in range(j+1,n+1):
        if l_s[i] < l_s[j] + l_s[j-1]:
            
            OK = j-1
            NG = 0
            while (OK - NG) > 1:
                mid = (OK+NG)//2
                if l_s[i] < l_s[j] + l_s[mid]:
                    OK = mid
                else:
                    NG = mid
            ans = ans + j - OK 
print(ans)



### FIXED CODE ###

n = int(input())
l_s = list(map(int,input().split()))
l_s.append(0)
l_s.sort()
ans = 0
#一番長い辺を選ぶ
#print(l_s)
for j in range(2,n):
    for i in range(j+1,n+1):
        if l_s[i] < l_s[j] + l_s[j-1]:
            
            OK = j-1
            NG = 0
            while (OK - NG) > 1:
                mid = (OK+NG)//2
                if l_s[i] < l_s[j] + l_s[mid]:
                    OK = mid
                else:
                    NG = mid
            ans = ans + j - OK 
print(ans)
### BUGGY CODE ###

from collections import Counter
from itertools import product

N = int(input())
S = input().strip()
dic = Counter(S)
c = dic.most_common()
mod = 10**9 + 7

ans = 0
d = []
for x in c:
    if x[1] == 1:
        break
    else:
        d.append(x[1])
b = len(c)-len(d)

ls =list(product([0, 1], repeat=len(d)))

for x in ls:
    num = 1
    for z, y in zip(d, x):
        if y == 1:
            num = (z*num)%mod
    ans = (ans + num*(2**b))%mod
print(ans-1)

### FIXED CODE ###

from collections import Counter
from itertools import product
 
N = int(input())
S = input().strip()
dic = Counter(S)
mod = 10**9 + 7

ans = 1
for x in dic:
    ans = ans*(dic[x]+1)%mod
print(ans-1)
### BUGGY CODE ###

from collections import deque
N,Q=map(int,input().split())
nondirtree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
rootflag=[0]*N
rootflag[0]=1
for i in range(N-1):
    a,b=map(int,input().split())
    nondirtree[a-1].append(b-1)
    nondirtree[b - 1].append(a - 1)
points=[tuple(map(int,input().split())) for _ in range(Q)]
#print(points)
v=0
d=deque()
d.append(v)
seen=[0]*N
seen[0]=1
score=[0]*N
ans=[0]*N
while len(d)!=0:
    v=d.popleft()
    for j in nondirtree[v]:
        if seen[j]==0:
            dirtree[v].append(j)
            seen[j]=1
            d.append(j)
    #print(d,seen,dirtree)
    #input(
#print(dirtree)
points=tuple(points)
for i in range(Q):
    score[points[i][0]-1]=score[points[i][0]-1]+points[i][1]
#print(score)
v=0
d=deque()
d.append(v)
for i in range(N):
    dirtree[i]=tuple(dirtree[i])
dirtree=tuple(dirtree)
score=tuple(score)
#print(dirtree)
ans[0]=score[0]
while len(d)!=0:
    v=d.popleft()
    for j in dirtree[v]:
        ans[j]=ans[v]+score[j]
        d.append(j)
    #input()
    #print(ans)
print(*ans,sep=" ")


### FIXED CODE ###

from collections import deque
N,Q=map(int,input().split())
nondirtree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
rootflag=[0]*N
rootflag[0]=1
for i in range(N-1):
    a,b=map(int,input().split())
    nondirtree[a-1].append(b-1)
    nondirtree[b - 1].append(a - 1)
points=[list(map(int,input().split())) for _ in range(Q)]
#print(points)
v=0
d=deque()
d.append(v)
seen=[0]*N
seen[0]=1
score=[0]*N
ans=[0]*N
while len(d)!=0:
    v=d.popleft()
    for j in nondirtree[v]:
        if seen[j]==0:
            dirtree[v].append(j)
            seen[j]=1
            d.append(j)
    #print(d,seen,dirtree)
    #input(
#print(dirtree)
for i in range(Q):
    score[points[i][0]-1]=score[points[i][0]-1]+points[i][1]
#print(score)
v=0
d=deque()
d.append(v)
ans[0]=score[0]
while len(d)!=0:
    v=d.popleft()
    for j in dirtree[v]:
        ans[j]=ans[v]+score[j]
        d.append(j)
    #input()
    #print(ans)
print(*ans,sep=" ")
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []

for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

for i in range(Q):
    for j in range(N):
        if A[j] == B[i]:
            A[j] = C[i]
    print(sum(A))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []

for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

S = sum(A)
memory = [0] * 100001
for num in A:
    memory[num] += 1

for i in range(Q):
    S_next = S + (C[i] - B[i]) * memory[B[i]]
    print(S_next)
    S = S_next
    memory[C[i]] += memory[B[i]]
    memory[B[i]] = 0
### BUGGY CODE ###

# D - People on a Line
import sys
sys.setrecursionlimit(10 ** 9)

n,m = map(int,input().split())
e = [[] for _ in range(n)]
for i in range(m):
  l,r,d = map(int,input().split())
  l -= 1
  r -= 1
  e[l].append((r,d))
  e[r].append((l,-d))

INF = float('inf')
c = [INF for _ in range(n)]

def dfs(u,x):
  c[u] = x
  for v,d in e[u]:
    if c[v] != INF:
      if c[v] == c[u]+d:
        continue
      else:
        print('No')
        exit()
    else:
      dfs(v,c[u]+d)

for i in range(n):
  if c[i] == INF:
    dfs(i,0)
print('Yes')


### FIXED CODE ###

# D - People on a Line
import sys
sys.setrecursionlimit(10 ** 9)

n,m = map(int,input().split())
e = [[] for _ in range(n)]
for i in range(m):
  l,r,d = map(int,input().split())
  l -= 1
  r -= 1
  e[l].append((r,d))
  e[r].append((l,-d))

INF = float('inf')
c = [INF for _ in range(n)]

def dfs(u,x):
  c[u] = x
  for v,d in e[u]:
    if c[v] != INF:
      if c[v] == c[u]+d:
        continue
      else:
        print('No')
        exit()
    else:
      dfs(v,c[u]+d)

for i in range(n):
  if c[i] == INF:
    dfs(i,0)
print('Yes')
### BUGGY CODE ###

mina=10**10
def waru(a,b):
  if a%b==0:
    return a//b
  else:
    return (a//b)+1
N,H=map(int,input().split())
A=list()
B=list()
for i in range(N):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
sb=sum(B)
for i in range(N):
  S=[k for k in B if k>A[i]]
  n=sum(S)
  if H-n<=0:
    mina=min(mina,len(S))
  else:
    mina=min(mina,waru(H-n,A[i])+len(S))
print(mina)

### FIXED CODE ###

import sys
mina=10**10
def waru(a,b):
  if a%b==0:
    return a//b
  else:
    return (a//b)+1
N,H=map(int,input().split())
A=list()
B=list()
for i in range(N):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
ma=max(A)
ind=A.index(ma)
B=[i for i in B if i>ma]
B=sorted(B,reverse=True)
cou=1
s=0
for i in range(len(B)):
  s+=B[i]
  if H<=s:
    print(i+1)
    sys.exit()
H=H-s
print(len(B)+waru(H,ma))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
h,n = map(int,readline().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,readline().split())
#  dp[i] i 以上の攻撃力を与えるための最小魔力
#b,a = zip(*sorted(zip(b,a))) #魔力でソート
dp = [0]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp[i] = 10**12
    for j in range(n):#すべての種類の魔法に対してループ
        if i -a[j] >= 0:#魔法が使えるなら
            dp[i] = min(dp[i],dp[i-a[j]]+b[j])
        else: dp[i] = min(dp[i],b[j])
"""print(dp)
print(a,b)"""
print(dp[h])


### FIXED CODE ###

#!/usr/bin/env python3
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
#  dp[i] i 以上の攻撃力を与えるための最小魔力
b,a = zip(*sorted(zip(b,a))) #魔力でソート
dp = [0]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp[i] = 10**12
    for j in range(n):#すべての種類の魔法に対してループ
        if i -a[j] >= 0:#魔法が使えるなら
            dp[i] = min(dp[i],dp[i-a[j]]+b[j])
        else: dp[i] = min(dp[i],b[j])
"""print(dp)
print(a,b)"""
print(dp[h])
### BUGGY CODE ###

def distinct_or_not(a_list):
    tmp_list = []
    for a in a_list:
        if a not in tmp_list:
            tmp_list.append(a)
        else:
            return 'NO'
    return 'YES'

n = int(input())
a_list = [int(a) for a in input().split()]

print(distinct_or_not(a_list))

### FIXED CODE ###

def distinct_or_not_2(a_list):
    a_list.sort()
    for i in range(len(a_list)-1):
        if a_list[i] == a_list[i+1]:
            return 'NO'
    return 'YES'

n = int(input())
a_list = [int(a) for a in input().split()]

print(distinct_or_not_2(a_list))
### BUGGY CODE ###

N = int(input())
A = [0]
A.extend(list(map(int, input().split())))

buka_num = []

for i in range(1,N):
    buka_num.append(A.count(i))
    
buka_num.append(0)
for ele in buka_num:
    print(ele)

### FIXED CODE ###

import collections
N = int(input())
A = [0]
A.extend(list(map(int, input().split())))
c = collections.Counter(A)
buka_num = []

for i in range(1,N):
    buka_num.append(c[i])
    
buka_num.append(0)
for ele in buka_num:
    print(ele)
### BUGGY CODE ###

N = int(input())
X = tuple(map(int,input().split()))
for i in range(len(X)):
    temp = list(X)
    temp.pop(i)
    test = int((len(temp)+1)/2)
    temp = sorted(temp)
    print(temp[test-1])


### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
X_sorted = sorted(X)
X_median = (N)/2
median1 = X_sorted[int(X_median)]
median2 = X_sorted[int(X_median-1)]
for i in range(N):
    if X[i] >=median1:
        print(median2)
    else:
        print(median1)
### BUGGY CODE ###

N, K = map(int, input().split())
score = list(map(int, input().split()))
add = []
sc = 1
for i in score:
    sc *= i
    add.append(sc)
pre = 0
for i in range(K - 1, N):
    if i == K - 1:
        cur = add[i]
    else:
        cur = add[i] // add[i - K]
        print("Yes" if cur > pre else "No")
    pre = cur


### FIXED CODE ###

N, K = map(int, input().split())
score = list(map(int, input().split()))
for i in range(K, N):
    print("Yes" if score[i - K] < score[i] else "No")
### BUGGY CODE ###

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

from fractions import gcd 

x =1
for i in l:
    x = x * i / gcd(x, i)

y=0
for j in range(n):
    y+=(x-1)%l[j]

print(int(y))

### FIXED CODE ###

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

from fractions import gcd 

x =1
for i in l:
    x = x * i // gcd(x, i)

y=0
for j in range(n):
    y+=(x-1)%l[j]

print(int(y))
### BUGGY CODE ###

N = int(input())
S = []
dic = {}
for i in range(N):
    a = str(input())
    if a not in S:
        S.append(a)
        dic[a] = 1
    else:
        dic[a] += 1
m = max(dic.values())
max_list = [kv[0] for kv in dic.items() if kv[1] == m]
max_list.sort()
for a in max_list:
    print(a)

### FIXED CODE ###

N = int(input())
S = [str(input()) for i in range(N)]
dic = {}
for a in S:
    if a not in dic:
        dic[a] = 1
    else:
        dic[a] += 1
m = max(dic.values())
max_list = [kv[0] for kv in dic.items() if kv[1] == m]
max_list.sort()
for a in max_list:
    print(a)
### BUGGY CODE ###

N= int(input())
A = list(map(int, input().split()))
B=[0]*N
for i in range(N):
    B[i]=A.count(i+1)
for i in range(N):
    B[A[i]-1]=B[A[i]-1]-1
    C = 0
    for j in range(N):

        if B[j]>1:
            C=C+B[j]*(B[j]-1)/2
    print(int(C))
    B[A[i] - 1] = B[A[i] - 1] +1


### FIXED CODE ###

import math
import collections

def cmb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
N = int(input())
M = input().split()

total = 0
count = collections.Counter(M)

for i in count.values():
    if i >= 2:
        total += cmb(i, 2)
    
for j in M:
    print(total - (count[j]-1))
### BUGGY CODE ###

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

for i in range(q):
    l,r = map(int,input().split())
    print(s[l-1:r].count("AC"))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
ac = [0] * (n+1)
num = 0

for i in range(n):
    if i != 0:
        if s[i-1:i+1] == "AC":
            num += 1
            
    ac[i+1] = num
    
for i in range(q):
    l,r = map(int,input().split())
    print(ac[r]-ac[l])
### BUGGY CODE ###

K, S = map(int, input().split())

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

### FIXED CODE ###

K, S = map(int, input().split())

ans = 0
for x in range(0, K+1):
  for y in range(0, K+1):
    z = S - x - y
    if 0 <= z <= K:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())

List = []
for i in range(1,10**4):
    for j in range(1,10**4):
        if N == i*j:
            List.append(i+j)

print(min(List)-2)

### FIXED CODE ###

#--------------------------------------------
#ライブラリ等
import sys
import math
from math import sqrt
input = sys.stdin.readline

#---------------------------------------------
N = int(input())
for i in range(int(sqrt(N))+1,-1,-1):
    if N % i == 0:
        print(int(i+(N/i)-2))
        exit()
### BUGGY CODE ###

import copy
N=int(input())
A=[int(input()) for _ in range(N)]

def delete(n):
  B=copy.deepcopy(A)
  del B[n]
  return(max(B))

for i in range(N):
  print(delete(i))

### FIXED CODE ###

import copy
N=int(input())
A=[int(input()) for _ in range(N)]

a=max(A)
k=A.count(a)#リストの最大数の個数をカウント
if k>=2:
  for i in range(N):
    print(a)
else:
  b=A.index(a)
  for i in range(N):
    if i != b:
      print(a)
    else:
      s=sorted(A)
      print(s[N-2])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
flag = True
b = []
for i in a:
    if b.count(i) != 0:
        flag = False
        break
    b.append(i)

if flag == True:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

n = int(input())
a = input().split()
b = set(a)
if len(a) == len(b):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
c=[0]*n
for i in range(1,n):
  c[i]=min(set(abs(h[i]-h[i-j])+c[i-j] for j in range(1,k+1) if i-j>=0))
print(c[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
hs = list(map(int, input().split()))
dp=[0]*n
dp[0]=0
for i, hi in enumerate(hs):
    if i == 0:
        continue
    s = max(0, i-k)
    dp[i] = min([ml + abs(hl - hi) for ml, hl in zip(dp[s:i], hs[s:i])])
print(dp[-1])
### BUGGY CODE ###

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

num_li = [0]*(10**6+1)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors



for i in range(n):
    num_li[ai[i]] += 1

ans = 0
    
for i in range(n):
    if num_li[ai[i]] > 1:
        continue
    #print(ai[i])
    flag = True
    div = make_divisors(ai[i])
    #print(div)
    for j in range(len(div)):
        if div[j] == ai[i]:
            continue
        #print(div[j],div)
        if num_li[div[j]] > 0:
            flag = False
            break
    if flag == True:
        ans += 1
    #exit()
print(ans)


### FIXED CODE ###

import math
n = int(input())
ai = [int(i) for i in input().split()]

ai.sort()

sqr_max_val = int(ai[n-1]**0.5)
max_val = ai[n-1]
#print(ai)
ai_ex = [0]*(2*10**6)
#ai_ex = [0]*(30)

for i in range(n):
    ai_ex[ai[i]-1] += 1

for i in range(n):
    if ai_ex[ai[i]-1] > 1:
        ai_ex[ai[i]-1] = 0
    """
    if ai[i] > sqr_max_val:
        break
    """
    tmp = ai[i]
    baisu = 2
    #print(ai[i])
    while tmp * baisu <=  max_val:
        ai_ex[tmp*baisu-1] = 0
        #print(tmp*baisu)
        baisu += 1
"""
for i in range(100):
    if ai_ex[i] == 1:
        a = 1
        #print(i)
"""
print(sum(ai_ex))
#print(ai_ex)
### BUGGY CODE ###

n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    if i+1 in fl:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while rmn:
        r = rmn.pop(0)
        alr.append(r)
        for nf in p[r-1]['T']:
            if not nf in tmp_fl:
                tmp_fl.append(nf)
            if not nf in rmn and not nf in alr:
                rmn.append(nf)
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    l = [i+1]+ dt['T'] + dt['B']
    for f in fl:
        if i+1 in f:
            ans[i] = len([x for x in f if not x in l])
            break
            

print(' '.join(map(str, ans)))


### FIXED CODE ###

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

def main():
    N,M,K = map(int,input().split())
    friend = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)
        
    brock = [[] for _ in range(N)]
    for _ in range(K):
        c,d = map(int,input().split())
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
    parent = [-1 for _ in range(N)]
    group = [0 for _ in range(N)]
    
    for i in range(N):
        put = []
        if parent[i] == -1:
            q = deque([i])
            parent[i] = i
            while q:
                now = q.pop()
                put.append(now)
                for fol in friend[now]:
                    if parent[fol] == -1:
                        parent[fol] = i
                        q.append(fol)
            l = len(put)
            for num in put:
                group[num] = l-1
                
        else:
            continue

    for i in range(N):
        group[i] -= len(friend[i])
        for dis in brock[i]:
            if parent[i] == parent[dis]:
                group[i] -= 1
    
    print(*group)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
S = list(map(int,input().split()))
counter = 0
for i in range(N):
  for j in range(N-1-i):
    for k in range(N -2 -i -j):
      a = S[i]
      b = S[i+j+1]
      c = S[i+j+k+2]
      if (a + b > c) and (c > abs(a - b)):
        counter += 1
    
print(counter)

### FIXED CODE ###

import bisect
N = int(input())
List = list(map(int,input().split()))
List.sort()
ans = 0
for i in range(N-1):
  for j in range(i+1, N):
    ans += bisect.bisect_left(List,List[i]+List[j])-(j+1)
print(ans)