Harryxun/stf_run huggingface dataset:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N, W = read_values()
    I = [tuple(read_values()) for _ in range(N)]

    w0 = I[0][0]
    if w0 > W:
        print(0)
        return

    dp = [
        [[0 for _ in range(N * 3 + 10)] for __ in range(N + 1)] for ___ in range(N + 1)
    ]

    for i, (w1, v) in enumerate(I):
        w = w1 - w0
        for k in range(N):
            for j in range(N * 3 + 5):
                dp[i + 1][k][j] = max(dp[i][k][j], dp[i + 1][k][j])
                dp[i + 1][k + 1][j + w] = max(dp[i][k][j] + v, dp[i + 1][k + 1][j + w])

    res = 0
    for vdp in dp:
        for k in range(N + 1):
            for i in range(W - k * w0 + 1):
                res = max(res, vdp[k][i])
    print(res)


if __name__ == "__main__":
    main()



### FIXED CODE ###

import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N, W = read_values()
    dp = [
        [[0 for _ in range(N * 3 + 10)] for __ in range(N + 10)]
        for ___ in range(N + 10)
    ]
    I = [tuple(read_values()) for _ in range(N)]

    w0 = I[0][0]
    if w0 > W:
        print(0)
        return

    for i, (w1, v) in enumerate(I):
        w = w1 - w0
        for k in range(N):
            for j in range(N * 3 + 5):
                dp[i + 1][k][j] = max(dp[i][k][j], dp[i + 1][k][j])
                dp[i + 1][k + 1][j + w] = max(dp[i][k][j] + v, dp[i + 1][k + 1][j + w])

    res = 0
    for k in range(N + 1):
        r = min(W - k * w0, 3 * N + 5)
        if r < 0:
            continue
        for i in range(r + 1):
            res = max(res, dp[N][k][i])
    print(res)


if __name__ == "__main__":
    main()
A , B , T = map(int , input()split())

count =  T // A * B

print(count)

### FIXED CODE ###

A , B , T = map(int , input().split())
 
count =  T // A * B
 
print(count)
import numpy as np
n, m = [int(i) for i in input().split()]

e = np.zeros([n,n])



for _ in range(m):
    a, b = [int(i) for i in input().split()]
    e[a-1,b-1] = b-1
    e[b-1,a-1] = a-1

ans = np.ones(n-1)
next_cand = [0]
cout = 0
check = np.zeros(n-1)
for next_ in next_cand:
    if cout == n-1:
        break
    connec = np.nonzero(e[next_,:])

    for i in connec[0]:

        i = int(i)
        if check[i-1] == 0:
            check[i-1] = 1
            cout +=1
            ans[i-1] = next_ +1
            next_cand.append(i)
            e[next_,:] = 0
            e[:,next_] = 0
            cout += 1
            if cout == n-1:
                break


print('Yes')

for i in ans:
    print(int(i))

### FIXED CODE ###

import numpy as np
from collections import deque
n, m = [int(i) for i in input().split()]

e = [ [] for i in range(n)]



for _ in range(m):
    a, b = [int(i) for i in input().split()]
    e[a-1].append(b-1)
    e[b-1].append(a-1)
    
    
q = deque()
q.append(0)
ans = np.ones(n-1)
check = np.zeros(n)

while len(q) > 0:
    # キューの先頭（左端）からnodeを取り出す
    node = q.popleft()

    if node is not None:
        check[node] = 2
        con = e[node]
        for i in con:
            if check[i] ==0:
                ans[i-1] = int(node) + 1
                q.append(i)
                check[i] = 1

        

print('Yes')

for i in ans:
    print(int(i))
def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans3 = cumsum(S)
    print(ans3)


def cumsum(S):
    """
    考えたときに累積和が浮かんだ
    ABCとあるので
    i文字目までのA相当の数、つまり?も含んだ数
    これをBとCにも適用する
    Aを決め打ちで進めるとBも走査することになる
    Cは定数倍で求められるが、|S|^2: TLE で意味がない

    ここで断念していろいろ調べると
    Bを決め打ちすれば
    A: 0-(B-1)
    C: (B+1)-N
    なのでNでおｋ

    と、思ったがWAと同じ間違いをしている
    3^q パターンをきちんと考える
    """
    n = len(S)
    aa = [0 for _ in range(n+1)]
    cc = [0 for _ in range(n+1)]
    q = [0 for _ in range(n+1)]
    for i in range(n):
        aa[i+1] += aa[i] + int(S[i] == "A")
        cc[i+1] += cc[i] + int(S[i] == "C")
        q[i+1] += q[i] + int(S[i] == "?")

    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(1, n-1):
        a = aa[i]
        c = cc[n] - cc[i+1]
        l = q[i]
        r = q[n] - q[i+1]
        # ABC の作り方
        # AB?: ? 1つをCに割り当てる
        # ?BC: ? 1つをAに割り当てる
        # ?B?: ? 2つをACに割り当てる
        if S[i] in ("B", "?"):
            ac = a * c * pow(3, l + r, MOD)
            aq, qc, qq = (0, 0, 0)
            if l + r - 1:
                p = pow(3, l + r - 1, MOD)
                aq = a * r * p
                qc = l * c * p
            if l + r - 1:
                qq = l * r * pow(3, l + r - 2, MOD)
            # print(a, c, l, r, ((l+r, l+r-1, l+r-2)), (ac, aq, qc, qq))
            # 3^x: xが負になるときに少数になってしまうので、float -> int にする必要がある
            # 上記が重いのでTLE: pow+mod引数で対応
            ans += ac + aq + qc + qq
            ans %= MOD

    return ans


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    """
    1 <= i < j < k <= |T|
    Ti = A
    Tj = B
    Tk = C
    """
    S = input()
    ans = editorial(S)

    print(ans)


def editorial(S):
    MOD = 10 ** 9 + 7
    n = len(S)
    dp = [[0] * (3+1) for _ in range(n+1)]

    for i in range(n, -1, -1):
        for j in range(3, -1, -1):
            if i == n:
                x = int(j == 3)
                # ≠3: 丸を3個つける前に最後の文字まで見終わってしまい、手遅れ
                # =3: 処理が正常終了
                dp[i][j] = x
            else:
                m1 = 1
                if S[i] == "?":
                    m1 = 3

                if j == 3:
                    # 丸は3個つけ終わったので、あとは?を置換するのみ
                    dp[i][j] = m1 * dp[i+1][j]
                else:
                    m2 = int(S[i] == "?" or S[i] == "ABC"[j])
                    # 前半:i文字目に丸をつけない場合, 後半:丸をつける場合に対応
                    dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

                dp[i][j] %= MOD

    ans = dp[0][0]
    return ans


if __name__ == '__main__':
    main()
from functools import reduce
n = int(input())
a = list(map(int, input().split()))

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

def gcd2(number):
    return reduce(gcd, number)

def lcm(x, y):
    return int(x * y / gcd(x, y))
def lcm2(number):
    return reduce(lcm, number)

m = lcm2(a) - 1
#print(m)
ans = 0
for i in range(n):
    ans += m % a[i]
print(ans)

### FIXED CODE ###

import fractions
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
m = lcm(*a)

ans = 0

for i in range(n):
    ans += (m - 1) % a[i]
print(int(ans))
a, b, x = map(int,input().split())
N = 0
if a%x ==0:
    N = int((b-a)//x)+1
else:
    c = a + (x-a%x)
    if b>=c:
        N = int((b-c)//x)+1
print(N)

### FIXED CODE ###

s = input()
A = 'A' + s[8] + 'C'
print(A)
N,M,C = map(int, input().split())
B = [int(_) for _ in input().split()]

count = 0
for i in range(len(N)):
  A = [_ for _ in input().split()] 
  sum = 0
  for j in range(M):
    sum = B[j]*A[j]
  if sum-C > 0:
    count += 1

print(count)

### FIXED CODE ###

N,M,C = map(int, input().split())
B = [int(_) for _ in input().split()]

count = 0
for i in range(N):
  A = [int(_) for _ in input().split()] 
  sum = 0
  for j in range(M):
    sum += B[j]*A[j]
  if sum+C > 0:
    count += 1

print(count)
DVSR = 998244353
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N = int(input())
INL = [II() for _ in range(N)]
SM = sum(INL)
HSM = SM//2

DP1 = [[0]*(SM+1) for _ in range(N+1)]
DP2 = [[0]*(SM+1) for _ in range(N+1)]
DP1[0][0] = 1
DP2[0][0] = 1

for value, i in enumerate(INL, 1):
    for j in range(SM+1):
        if j-value >= 0:
            DP1[i][j] = (2*DP1[i-1][j]+DP1[i-1][j-value])%DVSR
            DP2[i][j] = (DP2[i-1][j]+DP2[i-1][j-value])%DVSR
        else:
            DP1[i][j] = (2*DP1[i-1][j])%DVSR
            DP2[i][j] = DP2[i-1][j]

sub = 0
patall = POW(3, N)
for i in range(HSM+1, SM+1):
    sub += DP1[N][i]*3

if SM % 2 == 0:
    sub += 3*(DP1[N][HSM] - 2*DP2[N][HSM])
    sub += 3*DP2[N][HSM]

# print(DP2[N])
# print(SM)
print((patall - sub) % DVSR)

### FIXED CODE ###

DVSR = 998244353
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N = int(input())
INL = [II() for _ in range(N)]
SM = sum(INL)
HSM = SM//2

DP1 = [[0]*(SM+1) for _ in range(N+1)]
DP2 = [[0]*(SM+1) for _ in range(N+1)]
DP1[0][0] = 1
DP2[0][0] = 1

for i in range(1,N+1):
    value = INL[i-1]
    for j in range(SM+1):
        if j-value >= 0:
            DP1[i][j] = (2*DP1[i-1][j]+DP1[i-1][j-value])%DVSR
            DP2[i][j] = (DP2[i-1][j]+DP2[i-1][j-value])%DVSR
        else:
            DP1[i][j] = (2*DP1[i-1][j])%DVSR
            DP2[i][j] = DP2[i-1][j]

sub = 0
patall = POW(3, N)
for i in range(HSM+1, SM+1):
    sub += DP1[N][i]*3

if SM % 2 == 0:
    sub += 3*(DP1[N][HSM] - 2*DP2[N][HSM])
    sub += 3*DP2[N][HSM]

# print(DP2[N])
# print(SM)
print((patall - sub) % DVSR)
a = [int(input()) for i in range(N)]
flag = True

for i in range(N):
  if a[N-1] < a[i]:
    flag = False

if flag:
  print('Yay!')
else:
  print(':(')


### FIXED CODE ###

a = [int(input()) for i in range(6)]
flag = True

for i in range(6):
  for j in range(i+1, 6):
    if abs(a[i] - a[j]) > a[5]:
      flag = False

if flag:
  print('Yay!')
else:
  print(':(')
# -*- coding:utf-8 -*-

s = input().split()

if s[0] % 2 == 0 or s[1]%2 == 0:
  print("No")

else:
  print("Yes")

### FIXED CODE ###

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

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


if s[0]*s[1]%2 == 0:
    print("No")

else:
    print("Yes")
#encoding=utf-8
def solve(n):
    ans_a = calc_digit_sum(n)
    ans_b = calc_digit_sum(n - n % 10 - 1)
    ans_c = calc_digit_sum(10 ** (len(str(n)) - 1) - 1 + 10 ** (len(str(n)) - 1) * (int(str(n)[0]) - 1) )
    return max(ans_a, ans_b, ans_c)

def calc_digit_sum(n):
    str_n = str(n)
    ans = 0
    for x in range(len(str_n)):
        ans = ans + int(str_n[x])
    return ans

if __name__ == "__main__":
    n = int(input())
    print(solve(n))


### FIXED CODE ###

#encoding=utf-8
def solve(n):
    ans_a = calc_digit_sum(n)
    ans_b = calc_digit_sum(n - n % 10 - 1)
    ans_c = calc_digit_sum(10 ** (len(str(n)) - 1) - 1 + 10 ** (len(str(n)) - 1) * (int(str(n)[0]) - 1) )
    return max(ans_a, ans_b, ans_c)

def calc_digit_sum(n):
    if n <= 0:
        return 0
    str_n = str(n)
    ans = 0
    for x in range(len(str_n)):
        ans = ans + int(str_n[x])
    return ans

if __name__ == "__main__":
    n = int(input())
    print(solve(n))
def resolve():
    N,M=map(int,input().split())
    A=[list(map(int,input().split())) for i in range(N)]
    B=[list(map(int,input().split())) for i in range(M)]

    for i in A:
        valmin=10**5
        cnt=0
        for j in B:
            if abs(i[0]-j[0])+abs(i[1]-j[1])<valmin:
                valmin=abs(i[0]-j[0])+abs(i[1]-j[1])
                ans=cnt+1
            cnt+=1
        print(ans)
        
 resolve()

### FIXED CODE ###

# import bisect
# import copy
# import fractions
# import math
import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    N,M=map(int,input().split())
    A=np.array([[_ for _ in input()] for _ in range(N)])
    B=np.array([[_ for _ in input()] for _ in range(M)])

    #print(A[1:3][1:3])
    def main():
        for i in range(N-M+1):
            for j in range(N-M+1):
                if (A[i:i + M, j:j + M] == B).all():
                    return 'Yes'
                elif i==N-M and j==N-M:
                    return 'No'
    print(main())

resolve()
S = input()
L=len(S)
ans='No'
for i in S:
    if S[:(L-1)/2+1]==S[(L-1)/2+1::-1] and S[L+3/2:]==S[:(L+3/2)-1:-1]:
    ans='Yes'
print(ans)

### FIXED CODE ###

S = input()
L=len(S)
ans=0
S1=S[:(L-1)//2]
S2=S[((L+3)//2)-1:]
if (S==S[::-1]) & (S1==S1[::-1]) & (S2==S2[::-1]):
    ans='Yes'
else:
    ans='No'
print(ans)
s = input().split('T')
x, y = map(int, input().split())

h, v = [], []
for i, si in enumerate(s):
    if i % 2 == 0:
        h.append(len(si))
    else:
        v.append(len(si))

def search(move, goal, vertical):
    if vertical:
        goal -= move.pop(0)

    move.sort(reverse=True)
    for m in move:
        if goal > 0:
            goal -= m
        else:
            goal += m
    return goal == 0

if search(h, x, True) and search(v, y, True):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s = input().split('T')
x, y = map(int, input().split())

h, v = [], []
for i, si in enumerate(s):
    if i % 2 == 0:
        h.append(len(si))
    else:
        v.append(len(si))

def search(move, goal, horisontal):
    if horisontal:
        goal -= move.pop(0)

    move.sort(reverse=True)
    for m in move:
        if goal > 0:
            goal -= m
        else:
            goal += m
    return goal == 0

if search(h, x, True) and search(v, y, False):
    print('Yes')
else:
    print('No')
# -*- coding: utf-8 -*-
def main():
    n, q = inputAsIntArr()
    s = input()

    idxes = []
    for i in range(n):
        if s[i] != 'A':
            continue
        if s[i+1] == 'C':
            idxes.append(i)
            i += 1

    num_acs = ""
    for i in range(q):
        li, ri = inputAsIntArr()
        # num_ac = len([v for v in idxes if li-2 < v < ri-1])
        # num_acs += str(num_ac) + "\n"

    print(num_acs.strip())


def inputAsIntArr():
    return [int(i) for i in input().split(' ')]


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    # 累積出現数を格納: 指定される番号が1始まりなのでズラして格納
    p = [0] * (n+1)
    for i in range(n):
        p[i+1] = p[i] + (1 if s[i:i+2] == "AC" else 0)

    for i in range(q):
        l, r = map(int, input().split())
        # 終端(=l-1)から始端-1(=r-1)の累積出現数を引いた数が指定区間内での出現回数
        print(p[r-1] - p[l-1])


if __name__ == '__main__':
    main()
#ABC166
N,M=map(int,input().split())
H =list(map(int,input().split()))  #展望台の標高
A = list(range(M))
for i in range(M):
    a, b = map(int, input().split())
    if H[a-1]>H[b-1]:
        A[b-1] = 0
    elif H[a-1]<H[b-1]:
        A[a-1] = 0
    else:
        A[a-1] = 0
        A[b-1] = 0

print(N-A.count(0))

### FIXED CODE ###

#ABC166
N,M=map(int,input().split())
H =list(map(int,input().split()))  #展望台の標高
A = list(range(1,N+1))
for i in range(M):
    a, b = map(int, input().split())
    if H[a-1] > H[b-1]:
        A[b-1] = 0
    elif H[a-1] < H[b-1]:
        A[a-1] = 0
    else:
        A[a-1] = 0
        A[b-1] = 0
print(N-A.count(0))
N = list(map(int, input().split()))

if N%4 == 0:
    print("Yes")
    exit()

if N%7 == 0:
    print("Yes")
    exit()

S = N%7
K = (S%4)%2

if K == 0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N = int(input())

if N%4 == 0:
    print("Yes")

if N%4 == 1:
    if N < 21:
        print("No")
    else:
        print("Yes")

if N%4 == 2:
    if N < 14:
        print("No")
    else:
        print("Yes")


if N%4 == 3:
    if N < 7:
        print("No")
    else:
        print("Yes")
print('Yes' len(set(input())) == 3 else 'No')

### FIXED CODE ###

S = sorted(input())
if S[0] == 'a' and S[1] == 'b' and S[2] == 'c': print('Yes')
else: print('No')
n=input()
ps=input()

n=int(n[0])
ps=ps.split()
ps=[int(ps) for ps in ps]

output=0
for i-1 in range(n-2):
    if ps[i-1]<ps[i] and ps[i]<ps[i+1]:
        output=output+1
    elif ps[i+1]<ps[i] and ps[1]<ps[i-1]:
        output=output+1
    else:output=output+0
    
print(output)

### FIXED CODE ###

n=input()
ps=input()

ps=ps.split()
ps=[int(k) for k in ps]

output=0

for m in range(int(n)-2): 
    if ps[m]<ps[m+1] and ps[m+1]<ps[m+2]:
        output=output+1
    elif ps[m]>ps[m+1] and ps[m+1]>ps[m+2]:
        output=output+1
    else:
        output=output+0

print(output)
import os
import statistics

def quickSort(arr):
  left = []
  right = []
  if len(arr) <= 1:
   return arr
  median = int(statistics.median(arr))
  medianFlg = 0
  for element in arr:
   if element < median:
    left.append(element)
   elif element > median:
    right.append(element)
   else:
    medianFlg += 1
  left = quickSort(left)
  right = quickSort(right)
  return left + [median] * medianFlg + right

def binary_search1(list,target):
 result = -1
 left = 0
 right = len(list) - 1
 while left <= right:
  center = (left + right)//2
  if list[center] >= target:
   if list[center-1] < target:
    result = center
    break
   else: right = center - 1
  elif list[center] < target:
   if center==N-1:
    result = N
    break
   else:
    left = center + 1
 if result == -1:
  return 0
 else:
  return str(result)

def binary_search2(list,target):
 result = -1
 left = 0
 right = len(list) - 1
 while left <= right:
  center = (left + right)//2
  if list[center] <= target:
   if list[center+1] > target:
    result = N-center-1
    break
   else:  left = center + 1
  elif list[center] > target:
   if center==0:
    result = N-center
    break
   else:
    right =center - 1
 if result == -1:
  return 0
 else:
  return str(result)

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A=quickSort(A)
C=quickSort(C)
K=0
for i in range(N):
 L=int(binary_search1(A,B[i]))
 M=int(binary_search2(C,B[i]))
 K+=L*M
print(K)

### FIXED CODE ###

import bisect
N=int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
C.sort()
d=0
for i in B:
 d+=bisect.bisect_right(A,i-0.1)*(N-bisect.bisect_left(C,i+0.1))
print(d)
N,K = list(map(int,input().split()))
Hi = sorted(list(map(int,input().split())))

if len(Hi) <= K:
    print(0)
else:
    for num in range(K):
        Hi.pop((num+1)*-1)
    print(sum(Hi))

### FIXED CODE ###

N,K = list(map(int,input().split()))
Hi = list(map(int,input().split()))
Hi.sort()
Hi.reverse()

del Hi[:K]
print(sum(Hi))
n, k = map(int, input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans = []
for i in range(n):
    ans.append(h[i + k - 1] - h[i])
print(min(ans))

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans = []
for i in range(n - k + 1):
    ans.append(h[i + k - 1] - h[i])
print(min(ans))
n=int(input())
if n%10==7:
	print('Yes')
	exit()
else:
	n=n//10
	if n%10==7:
		print('Yes')
		exit()
	else:
		n=n//10:
		if n%10==7:
			print('Yes')
			exit()
print('No')

### FIXED CODE ###

n=input()
if n[0]=='7' or n[1]=='7' or n[2]=='7':
	print('Yes')
else:
	print('No')
abc = map(int,input().split())
"YES" if sum(abc) == 17 and abc.count(5) else "NO"

### FIXED CODE ###

abc = list(map(int,input().split()))
print("YES" if sum(abc) == 17 and abc.count(5) else "NO")
a, b, c = map(int, input().split())
lis = list(map(int, input().split()))
lis.sort()
print(lis[2]*10 + lis[1] + lis[0])

### FIXED CODE ###

lis = list(map(int, input().split()))
lis.sort()
print(lis[2]*10 + lis[1] + lis[0])
n, m = map(int, input().split())
a = []
b = []
for i in range(n):
    a += list(map(int, input().split()))
for i in range(m):
    b.append(int(input()))
for i in range(n):
    c = 0
    for j in range(m):
        c += a[i][j] * b[j]
    print(c)


### FIXED CODE ###

n, m = map(int, input().split())
A = [map(int, input().split()) for _ in [None] * n]
b = [int(input()) for _ in [None] * m]
for a in A:
    print(sum(i * j for i, j in zip(a, b)))
import bisect
N = int(input())
l = list(map(int,input().split()))
l.sort()
ans =0
for i in range(1,n):
    for j in range(i):
        p = l[i]+ l[j]
        q = bisect.bisect_left(l,p)
        ans += q-i-1

print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
ans =0
for i in range(1,n):
    for j in range(i):
        p = l[i]+ l[j]
        q = bisect.bisect_left(l,p)
        ans += q-i-1

print(ans)
N = int(input())
#N,M = map(int,input().split())
#A = list(map(int,input().split()))
#A = [list(map(int,input().split())) for i in range(N)]
def prime_dict(n):
    a = {}
    if n%2 == 0:
        a[2] = 1
        n//=2
    while n%2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f*f <= n:
        if n%f == 0:
            if f not in a:
                a[f] == 1
            else:
                a[f] += 1
        else:
            f += 2
    if n!= 1:
        a[n] = 1
    return a
ans = 1
mod = 10**9+7
prime2 = {}
for i in range(2,N+1):
    prime = prime_dict(i)
    for k,v in prime.items():
        if k not in prime2:
            prime2[k] = v
        else:
            prime2[k] += v
for i in prime2.values():
    ans = (ans*(i+1))%mod
print(ans)


### FIXED CODE ###

N = int(input())
#N,M = map(int,input().split())
#A = list(map(int,input().split()))
#A = [list(map(int,input().split())) for i in range(N)]
def primes(n):
    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
    return [i for i in range(n + 1) if is_prime[i]]
ans = 1
mod = 10**9+7
prime = primes(N)
for i in prime:
    isum = 0
    for n in range(2,N+1):
        while n%i == 0:
            isum += 1
            n //= i
    ans = (ans*(isum+1))%mod
print(ans)
import sys
from itertools import count, accumulate
from operator import mul
from functools import reduce
lines = sys.stdin.readlines()

positions = [int(i) for i in lines[1].split(' ')]

distances = [ j - i for i, j in zip(positions, positions[1:])]

n = len(distances)
factorials = [1] + list(accumulate(range(1,n + 1), mul))

combinations = dict()
def combination(i, j):
    if (i, j) in combinations:
        return combinations((i, j))
    else:
        return factorials[i] // (factorials [j] * factorials[i - j])

permutations = dict()
def permutation(i, j):
    if (i, j) in permutations:
        return permutations((i, j))
    else:
        return reduce(mul, range(j, i+1))

s = 0
result = 0
for d, i in zip(distances, count(1)):
    lt = i - 1
    gt = n - i
    t = factorials[lt] * combination(n, gt) * factorials[gt]
    s += t
    result += d * s

print(int(result % (pow(10,9) + 7)))

### FIXED CODE ###

import sys
lines = sys.stdin.readlines()
n = lines.pop(0)
e = lines.pop(-1).strip()
r = 0
s = False
for l in lines:
    l = l.strip()
    n, t = l.split(' ')
    if s:
        r += int(t)
    elif n == e:
        s = True
print(r)
x=input()
print(x**3)


### FIXED CODE ###

a=input()
print a**3