Harryxun/stf_run huggingface dataset:
import sys
readline = sys.stdin.readline


def chmax(a, b):
    """
    2値の大きい値を返す

    Args:
        a   (int)   : 値１
        b   (int)   : 値２
    Return:
        a   (int)   : aまたはbの大きい値
    """
    if a < b:
        a = b
    return a


def main():

    N, W = map(int, readline().split())

    # knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
    # knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
    knapsack = [list(map(int, readline().split())) for _ in range(N)]

    # db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for n in range(1, N + 1):
        for w in range(W + 1):
            if w - knapsack[n - 1][0] < 0:
                dp[n][w] = dp[n - 1][w]
            else:
                dp[n][w] = chmax(dp[n - 1][w], dp[n - 1]
                                 [w - knapsack[n - 1][0]] + knapsack[n - 1][1])

    print(dp[N][W])


if __name__ == "__main__":
    main()


### FIXED CODE ###

# --------------------------------------
# 関数定義
# --------------------------------------


def chmin(a, b):
    if a > b:
        a = b
    return a

# --------------------------------------
# メイン処理
# --------------------------------------


def main():
    INF = 10 ** 10
    N = int(input())
    h = list(map(int, input().split()))

    dp = [INF] * N
    dp[0] = 0

    for i in range(1, N):
        dp[i] = chmin(dp[i], dp[i-1] + abs(h[i]-h[i-1]))
        if i >= 2:
            dp[i] = chmin(dp[i], dp[i-2] + abs(h[i]-h[i-2]))

    print(dp[N - 1])


# --------------------------------------
# 実行
# --------------------------------------
if __name__ == "__main__":
    main()
N, M = map(int, input().split())
V = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(lambda x: int(x) - 1, input().split())
    V[x].append(y)

dp = [None for _ in range(N)]

def dfs(x):
    if dp[x] is not None:
        return dp[x]
    if not V[x]:
        dp[x] = 0
        return 0
    l = max(dfs(v) for v in V[x]) + 1
    dp[x] = l
    return l

print(max(dfs(v) for v in range(N)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5)

N, M = map(int, input().split())
V = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(lambda x: int(x) - 1, input().split())
    V[x].append(y)

dp = [None for _ in range(N)]

def dfs(x):
    if dp[x] is not None:
        return dp[x]
    if not V[x]:
        dp[x] = 0
        return 0
    l = max(dfs(v) for v in V[x]) + 1
    dp[x] = l
    return l

print(max(dfs(v) for v in range(N)))
t = input()
o = ""
for i in range(len(t)):
    if t[i] == "?":
        if t[i - 1] == "P":
            o += "D"
        elif t[i + 1] == "D":
            o += "P"
        else:
            o += "D"
    else:
        o += t[i]

print(o)

### FIXED CODE ###

print(input().replace('?','D'))
n=int(input())
l=[input() for i in range(n)]
target_song = input()

total = 0

ff = False

for i in l:
    s, t = i.split(" ")

    if s == target_song:
        f = True
        continue
        
    if f == True:
        total +=  int(t)

print(total)

### FIXED CODE ###

n=int(input())
l=[input() for i in range(n)]
target_song = input()

total = 0

ff = False

for i in l:
    s, t = i.split(" ")

    if s == target_song:
        ff = True
        continue
        
    if ff == True:
        total +=  int(t)

print(total)
import numpy as np
while True:
    n= int(input())
    if n == 0:
        break
    print(np.std(list(map(int, input().split()))))

### FIXED CODE ###

while True:
    n = int( input() )
    if n==0:
        break
    a=list(map(int, input().split()))
    m=sum(a)/n
    s=0
    for i in a:
        s+=(i-m)**2
    print( ( s/n)**0.5 )
import bisect
import sys


N = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    to[u].append(v)
    to[v].append(u)
del u, v

ans = [-1] * N


def dfs(v, dp):
    # dp は参照渡し
    if len(dp) == 0 or a[v] > dp[-1]:
        dp.append(a[v])
        back = -1
    else:
        pos = bisect.bisect_left(dp, a[v])
        back = dp[pos]
        dp[pos] = a[v]
    ans[v] = len(dp)

    for u in to[v]:
        if ans[u] == -1:
            dfs(u, dp)
    if back == -1:
        dp.pop()
    else:
        dp[pos] = back


sys.setrecursionlimit(10 ** 6)
dfs(0, [])


for an in ans:
    print(an)


### FIXED CODE ###

K = int(input())
A, B = map(int, input().split())

for i in range(A, B + 1):
    if i % K == 0:
        ans = "OK"
        break
else:
    ans = "NG"
print(ans)
S = int(input())
h = S // 3600
m  = (S % 3600) // 60
s = S % 3600

print(h:m:s)

### FIXED CODE ###

S = int(input())
h = int(S // (60*60))
m = int(S / 60) % 60
s = S%60

print('{}:{}:{}'.format(h,m,s))
import fractions
from functools import reduce

def lcm_b(a, b):
        #print("base",a,b)
        return (a * b) // fractions.gcd(a, b)

def lcm_o():
        global n
        return reduce(lcm_b, n)

def chk(v):
        global n
        for i in range(1,30):
                if v%2 == 1:break
                v = v//2
        t=2**(i-1)
        for j in range(len(n)):
                s=n[j]/t
                if n[j] % t == 0 and s % 2 == 1:
                        n[j] = int(s)

                else: return 0
        return t/2

def mp(v):
        if v%2==1:v+=1
        return int(v//2)

N,M= [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
n=sorted(set(n),reverse = True)
bs = n[0]

if len(n) > 1:
        c = chk(n[-1])
        if  c != 0:
                v = lcm_o()*c
                if v > M: print(0) 

                else: print(mp(M//v))
        
        else: print(0)
        
elif len(n)==1: print(mp(M//(bs*0.5)))

### FIXED CODE ###

import fractions
from functools import reduce
N,M= [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
#print(n)
n=sorted(set(n),reverse = True)
bs = n[0]
#print(n)
#c=len(n)
 
 
def lcm_b(a, b):
        #print("base",a,b)
        return (a * b) // fractions.gcd(a, b)
 
def lcm_o():
        global n
        return reduce(lcm_b, n)
 
def chk(v):
        global n
        for i in range(1,30):
                if v%2 == 1:break
                v = v//2
        t=2**(i-1)
        for j in range(len(n)):
                if n[j] % t == 0 and (n[j] / t) % 2 == 1:
                        n[j] = int(n[j]/t)
                else: return 0
        return i-1
 
if len(n) > 1:
        
        c = chk(n[-1])
        
        if  c != 0:
                v = lcm_o()*(2**(c-1))
                
                if v > M:
                        print(0) 
                else:
                        v = M//v
                        if v%2==1: v+=1
                        print(int(v//2))
        
        else: print(0)
elif len(n)==1:
        v = int(bs*0.5)
        v = M//v
        if v%2==1: v+=1
        print(int(v//2))
a,b,c = map(int,input().split())

int T = 0

if a+b == c:
    T = 1
elif b+c == a:
    T = 1
elif a+c == b:
    T = 1

if T == 1:
    print('YES')
else:
    print('NO')




### FIXED CODE ###


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

#list 並び替え→最初と最後足して == 真ん中　ならばYES!!!

can.sort()

if can[0]+can[1] == can[2]:
    print("Yes")
else:
    print("No")
r = int(input())
pi = 3.14159265358979

l = 2 * pi * r
s = pi * r**2

print("{0} {1}".format(s, l))

### FIXED CODE ###

r = float(input())
pi = 3.14159265358979

l = 2 * pi * r
s = pi * r**2

print("{0} {1}".format(s, l))
pi = 3.14159
r = int(input())
print(r*r*pi,2*r*pi)

### FIXED CODE ###

pi = 3.14159265358979
r = float(input())
print("{0:.6f}".format(r*r*pi),"{0:.6f}".format(2*r*pi))
def dfs(pos, not_pos, tree_dict, ans_li, length):
  n_li = tree_dict[pos]
  for n, w in n_li:
    if n == not_pos:
      continue
    new_length = length+w
    if new_length%2 == 0:
      ans_li[n] = 0
    else:
      ans_li[n] = 1
    ans = dfs(n, pos, tree_dict, ans_li, new_length)
  return ans_li

def run():
  N = int(input())
  tree_dict = {}
  ans_li = [0]*(N+1)
  for n in range(N-1):
    u, v, w = map(int, input().split())
    tree_dict.setdefault(u, []).append((v, w))
    tree_dict.setdefault(v, []).append((u, w))
  length = 0
  ans = dfs(1, -1, tree_dict, ans_li, length)
  for a in ans[1:]:
    print(a)
    

if __name__ == '__main__':
  run()

### FIXED CODE ###

import sys
sys.setrecursionlimit(500*500)

def dfs(pos, not_pos, tree_dict, ans_li, length):
  n_li = tree_dict[pos]
  for n, w in n_li:
    if n == not_pos:
      continue
    new_length = length+w
    if new_length%2 == 0:
      ans_li[n] = 0
    else:
      ans_li[n] = 1
    ans = dfs(n, pos, tree_dict, ans_li, new_length)
  return ans_li

def run():
  N = int(input())
  tree_dict = {}
  ans_li = [0]*(N+1)
  for n in range(N-1):
    u, v, w = map(int, input().split())
    tree_dict.setdefault(u, []).append((v, w))
    tree_dict.setdefault(v, []).append((u, w))
  length = 0
  ans = dfs(1, -1, tree_dict, ans_li, length)
  for a in ans[1:]:
    print(a)
    

if __name__ == '__main__':
  run()
N=int(input())
a=list(map(int,input().split()))
ans=[]
b=0
if N==1:
    print(0)
else:
    for i in range(min(a),max(a)):
        for k in range(N):
            b+=(a[k]-i)**2
        ans.append(b)
        b=0
    print(min(ans))

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
ans=[]
b=0
if N==1:
    print(0)
else:
    for i in range(min(a),max(a)+1):
        for k in range(N):
            b+=(a[k]-i)**2
        ans.append(b)
        b=0
    print(min(ans))
import sys
N,K=map(int, input().split())
p=[]
for i in range (0,N):
  r=list(map(int, input().split() )) 
  p.append(r)
p.sort()
q=[]
for i in range(0,N):
  q+=[p[i][0]]*p[i][1]
  if len(q)>K;
    print(q[K-1])
    sys.exit()

### FIXED CODE ###

import sys
N,K=map(int, input().split())
p=[]
for i in range (0,N):
  r=list(map(int, input().split() )) 
  p.append(r)
p.sort()
k=0
for i in range(0,N):
  k+=p[i][1]
  if k>=K:
    print(p[i][0])
    sys.exit()
a=list(map(int,input().split()))
b=len(a)
c=[a]
w=0
for i in range(b-1):
    c.append(list(map(int,input().split())))
N=int(input())
d=[]
for y in range(N):
    d.append(int(input()))
for n in d:
    for p in c:
        for j in p:
            if n in j:
                j=0
for t in c:
    for h in t:
        if c.count(0)==b:
            o=1
            break
    else:
        continue
    break
for v in range(b):
    w=0
    for k in c:
        if k[v]==0:
            w+=1
        if w==b:
            o=1
w=0
for ji in range(b):
    if c[ji][ji]==0:
        w+=1
    if w==b:
        o=1
w=0
for ji2 in range(b):
    if c[ji2][b-ji2]==0:
        w+=1
    if w==b:
        o=1
for v1 in range(b):
    w=0
    for k in range(b):
        if c[k][v1]==0:
            w+=1
        if w==b:
            o=1

if o==1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

p1=list(map(int,input().split()))
p2=list(map(int,input().split()))
p3=list(map(int,input().split()))
p=p1+p2+p3
n=int(input())
for _ in range(n):
    b=int(input())
    if b in p:
        p[p.index(b)]=0
if p[0]+p[1]+p[2]==0 or p[3]+p[4]+p[5]==0 or p[6]+p[7]+p[8]==0 or p[0]+p[3]+p[6]==0 or p[1]+p[4]+p[7]==0 or p[2]+p[5]+p[8]==0 or p[0]+p[4]+p[8]==0 or p[2]+p[4]+p[6]==0:
    print("Yes")
else:
    print("No")
import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(2*n-1)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    
n=int(input())
hi=[int(k) for k in input().split()]
co=[int(k) for k in input().split()]
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(ans)  
      


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    

n = int(raw_input())
hi = list(map(int,raw_input().split()))
co= list(map(int,raw_input().split()))
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(segTree.query(0,0,n-1,0,n-1))
a = []
n = int(input())
for i in range(n):
    key,value = input().split()
    a.append((key,value,int(i+1)))
a.sort(key=lambda x:(x[0],reverse = not x[1]))
for i in range(n):
    print(a[i][2])

### FIXED CODE ###

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

p = 3*a + p

pi = p // 2

print(pi)
from collections import deque
N, M = map(int, input().split())
A = list(int(input()) for _ in range(M))
A = deque(A)
P = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
a = A.popleft()
if 1 == a:
    dp[1] = 0
    a = A.popleft()

for i in range(2, N+1):
    if i != a:
        dp[i] = (dp[i-1] + dp[i-2]) % P
    else:
        dp[i] = 0
        if len(A):
            a = A.popleft()
print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
if N == 1:
    print(1)
    quit()
if M > N//2:
    print(0)
    quit()

A = list(int(input()) for _ in range(M))
idx = 0
P = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
a = -1
if len(A):
    if 1 == A[idx]:
        dp[1] = 0
        if idx < M-1:
            idx += 1

if len(A):
    for i in range(2, N+1):
        if i != A[idx]:
            dp[i] = (dp[i-1] + dp[i-2]) % P
        else:
            dp[i] = 0
            if idx < M-1:
                idx += 1
else:
    for i in range(2, N+1):
        dp[i] = (dp[i-1] + dp[i-2]) % P
print(dp[N])
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
S = [0] * (N+1)
m = [0] * (M+1)
ans = 0
for i in range(N):
    S[i+1] = (S[i] + A[i]) % M
for s in S:
    ans += m[s]
    m[s] += 1
print(ans)


### FIXED CODE ###

from collections import defaultdict
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
S = [0] * (N+1)
m = defaultdict(int)
ans = 0
for i in range(N):
    S[i+1] = (S[i] + A[i]) % M
for s in S:
    ans += m[s]
    m[s] += 1
print(ans)
X = int(input())
print("YNeos")[X>29::2]

### FIXED CODE ###

X = int(input())
print("YNeos"[not(X>=30)::2])
x,y,z=map(int,input(" "))
if pow(z, 0.5)>pow(x, 0.5)+pow(y, 0.5):
	print("Yes")
else:

	print("No")

### FIXED CODE ###

import math
x,y,z=map(int,input().split(" "))

if (z-y-x)**2>4*x*y and z>y and z>x:
	print("Yes")
else:
 
	print("No")
# coding: utf-8
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

@lru_cache(maxsize = None)
def f2(i, j, a):
    if i == j:
        return(a[i])
    return(max(a[i] - f2(i + 1, j, a), a[j] - f2(i, j - 1, a)))

n = int(input()) # 1 <= n <= 3000
a = list(map(int, input().split()))
print(f2(0, n - 1, a))

### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, a):
    dp = [[0] * n for _ in range(n)]
    # dp[i][i] を a[i] で初期化
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        dpi = dp[i]
        dpi1 = dp[i + 1]
        for j in range(i + 1, n):
            r = a[i] - dpi1[j]
            l = a[j] - dpi[j - 1]
            dp[i][j] = r if r > l else l
            # dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return(dp[0][-1])

n = int(input()) # 1 <= n <= 3000
a = list(map(int, input().split()))
print(f(n, a))
a,b=input().split()
print((int(a)-1)*(int(b)-))

### FIXED CODE ###

a,b=input().split()
print((int(a)-1)*(int(b)-1))
n, m = map(int(input().split())
print((n-1)*(m-1))

### FIXED CODE ###

n, m = map(int, input().split())
print((n-1)*(m-1))
k,n=map(int,input().split())
a=list(map(int,input().split()))
a.append(k+a[0])
 
for i in range(1,n):
  l=max(a[i]-a[i-1])
 
print(k-l)

### FIXED CODE ###

k,n=map(int,input().split())
a=list(map(int,input().split()))
a.append(k+a[0])

l=0
for i in range(1,n+1):
  l=max(l,a[i]-a[i-1])
 
print(k-l)
N = int(input())
A = [int(i) for i in input().split()]

S = min(A)
L = max(A)

c = 0
B = []

if S == L:
    pass

elif abs(L) >= abs(S):
    l = A.index(L)
    if A[0] < 0:
        A[0] += L
        c += 1
        B.append((l+1, 1))
    for i in range(N-1):
        if A[i+1] >= A[i]:
            pass
        else:
            if A[i+1] < 0:
                A[i+1] += L
                c += 1
                B.append((l+1, i+2))
            A[i+1] += A[i]
            c += 1
            B.append((i+1, i+2))
            if i+1 == l:
                L = A[l]

else:
    if A[-1] > 0:
        A[-1] += S
        c += 1
        B.append((s+1, N))
    for i in range(N-1):
        if A[-i-2] <= A[-i-1]:
            pass
        else:
            if A[-i-2] > 0:
                A[-i-2] += S
                c += 1
                B.append(s+1, N-i-1)
            A[-i-2] += A[-i-1]
            c += 1
            B.append((N-i, N-i-1))
            if -i-2 == s:
                S = A[s]


if c == 0:
    print(c)
else:
    print(c)
    for i in range(c):
        print(B[i][0], B[i][1])


### FIXED CODE ###

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

S = min(A)
L = max(A)

c = 0
B = []

if S == L:
    pass

elif S >= 0 and L > 0:
    for i in range(N-1):
        if A[i+1] >= A[i]:
            pass
        else:
            A[i+1] += A[i]
            c += 1
            B.append((i+1, i+2))

elif L <= 0 and S < 0:
    for i in range(N-1):
        if A[-i-2] <= A[-i-1]:
            pass
        else:
            A[-i-2] += A[-i-1]
            c += 1
            B.append((N-i, N-i-1))

else:
    if L >= -S:
        l = A.index(L)
        if A[0] < 0:
            A[0] += L
            c += 1
            B.append((l+1, 1))
        for i in range(N-1):
            if A[i+1] >= A[i]:
                pass
            else:
                if A[i+1] < 0:
                    A[i+1] += L
                    c += 1
                    B.append((l+1, i+2))
                A[i+1] += A[i]
                c += 1
                B.append((i+1, i+2))
                if i+1 == l:
                    L = A[l]
    else:
        s = A.index(S)
        if A[-1] > 0:
            A[-1] += S
            c += 1
            B.append((s+1, N))
        for i in range(N-1):
            if A[-i-2] <= A[-i-1]:
                pass
            else:
                if A[-i-2] > 0:
                    A[-i-2] += S
                    c += 1
                    B.append((s+1, N-i-1))
                A[-i-2] += A[-i-1]
                c += 1
                B.append((N-i, N-i-1))
                if -i-2 == s:
                    S = A[s]

if c == 0:
    print(c)
else:
    print(c)
    for i in range(c):
        print(B[i][0], B[i][1])
N, K = list(map(int, input().split()))
D = list(map(int, input().split()))
number = [i for i in range(10)]
num_lis = list(set(number) - set(D))
ans=[]
for i in num_lis:
    for j in num_lis:
        for k in num_lis:
            for l in num_lis:
                a = 1000*i + 100 *j + 10*k + l
                if a>=N:
                    ans.append(a)
print(ans[0])

### FIXED CODE ###

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

number = [i for i in range(10)]
num_lis = list(set(number) - set(D))
ans=[]
for i in range(N, 100000):
    a=i//10000
    if bool((a not in D) or i <10000):
        b=i//1000 - 10*a
        if bool((b not in D) or i <1000):
            c=i//100 - 100 * a - 10 * b
            if bool((c not in D) or i < 100):
                d= i//10 - 1000 * a - 100*b - 10*c
                if bool((d not in D) or i <10):
                    e=i%10
                    if e not in D:
                        ans.append(i)
print(ans[0])
i=0
while 1:
    a=int(input())
    if(a==0)break
    i+=1
    print("Case {0}: {1}".format(i,a))

### FIXED CODE ###

i=0
while 1:
    a=int(input())
    if(a==0): break
    i+=1
    print("Case {0}: {1}".format(i,a))
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
S = []
for i in [0]*H:
    l = input()
    S.append([1 if x == "#" else -1 for x in l])

bk = 0
wh = 0
def check(S, x, y):
    global bk, wh
    n = S[y][x]
    if n == 0:
        return 
    elif n == 1:
        bk += 1
    elif n == -1:
        wh += 1
    S[y][x] = 0
    if 0 < y and S[y-1][x] == -n:
        check(S, x, y-1)
    if 0 < x and S[y][x-1] == -n:
        check(S, x-1, y)
    if y < H-1 and S[y+1][x] == -n:
        check(S, x, y+1)
    if x < W-1 and S[y][x+1] == -n:
        check(S, x+1, y)
    return 

cnt = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == 1:
            check(S, x, y)
            cnt += wh*bk
            wh = 0
            bk = 0
            
print(cnt)

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

H, W = map(int, input().split())
S = []
for i in [0]*H:
    l = input()
    S.append([1 if x == "#" else -1 for x in l])

bk = 0
wh = 0
def check(S, x, y):
    global bk, wh
    n = S[y][x]
    if n == 0:
        return 
    elif n == 1:
        bk += 1
    elif n == -1:
        wh += 1
    S[y][x] = 0
    if 0 < y and S[y-1][x] == -n:
        check(S, x, y-1)
    if 0 < x and S[y][x-1] == -n:
        check(S, x-1, y)
    if y < H-1 and S[y+1][x] == -n:
        check(S, x, y+1)
    if x < W-1 and S[y][x+1] == -n:
        check(S, x+1, y)
    return 

cnt = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == 1:
            check(S, x, y)
            cnt += wh*bk
            wh = 0
            bk = 0
            
print(cnt)
w=input()
alphabet=[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]
flag=0
for i in alphabet:
	num=w.count(i)
	if num%2==1:
		flag=1
		break
if flag==0:
	print("Yes")
else:
	print("No")

### FIXED CODE ###

w=input()
alphabet=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
flag=0
for i in alphabet:
	num=w.count(i)
	if num%2==1:
		flag=1
		break
if flag==0:
	print("Yes")
else:
	print("No")
i = 1
while True:
    x = int(input().strip())
    if x == 0:
        break
    else:
        print ("Case" '#{0}: #{1}').format(i,x)
        i += 1

### FIXED CODE ###

i = 1
while True:
    x = int(input().strip())
    if x == 0:
        break
    else:
        print ("Case {}: {}".format(i,x))
        i += 1
n=int(input())
lst=list(map(int,input().split()))
count=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(k+1,n):              
            a=lst[i]
            b=lst[j]
            c=lst[k]
            if a<b+c and b<c+a and c<a+b:
                    count+=1
print(count)


### FIXED CODE ###

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