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

import sys
from collections import deque

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

H, W = map(int, readline().split())
S = tuple(read().split())


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    while queue:
        x, y = queue.popleft()
        visited[x][y] = True

        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and not visited[new_x][new_y]:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return distance


answer = 0
limit = H - 1 + W - 1
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue

        cnt = 0
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = dy + j, dx + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if S[new_x][new_y] == '.':
                    cnt += 1

        if cnt > 2:
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp
        if answer == limit:
            print(answer)
            exit()

print(answer)


### FIXED CODE ###

import sys
from collections import deque

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

H, W = map(int, readline().split())
S = [list(input()) for i in range(H)]


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    while queue:
        x, y = queue.popleft()
        if visited[x][y]:
            continue
        visited[x][y] = True

        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and not visited[new_x][new_y]:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return distance


answer = 0
limit = H - 1 + W - 1
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue

        cnt = 0
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = dy + j, dx + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if S[new_x][new_y] == '.':
                    cnt += 1

        if cnt > 2:
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp
        if answer == limit:
            print(answer)
            exit()

print(answer)
### BUGGY CODE ###

import math

def segment_sieve(a, b):
    is_prime = [True] * (b - a)
    sqrt_b = math.ceil(math.sqrt(b))
    is_prime_small = [True] * (sqrt_b)

    i = 2
    while i * i < b:
        if is_prime_small[i]:
            j = 2 * i
            while j * j < b:
                is_prime_small[j] = False
                j += i

            j = max(2, round((a + i - 1) // i)) * i
            while j < b:
                is_prime[j - a] = False
                j += i

        i+=1
        
    return is_prime

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

minimum = (min(l for l, r in LR) + 1) // 2
maximum = max(r for l, r in LR)
minimum = 0
primes = sieve(maximum + 1)
for l, r in LR:
    count = 0
    for i, v in enumerate(primes):
        if i + minimum >= l and i + minimum > 1 and i + minimum <= r and (i + minimum) % 2 == 1 and v and primes[(i + minimum + 1) // 2 - minimum]:
            count += 1
    print(count)


### FIXED CODE ###

import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

primes = sieve(100000 + 1)
c = [0] * (100000 + 2)

for i, v in enumerate(primes):
    if v and i > 1 and i % 2 == 1 and primes[(i + 1) // 2]:
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]

for l, r in LR:
    print(c[r]-c[l-1])
### BUGGY CODE ###

n=int(input())
L=list(map(int,input().split()))
L.sort(reverse=True)
def tri(a,b,c):
    if a<b+c:
        return 1
    else:
        return 0
count=0
for i in range(0,n-2):
    k=L[i]
    for j in range(i+1,n-1):
        t=L[j]
        for m in range(j+1,n):
            if tri(k,t,L[m])==1:
                count+=1
print(count)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
def nibuta(a,x):
    h=len(a)
    if a[0]>=x:
        return 0
    elif a[h-1]<x:
        return h
    else:
        lo=-1
        up=h-1
        while up-lo>1:
            if a[(lo+up)//2]>=x:
                up=(lo+up)//2
            else:
                lo=(lo+up)//2
        if a[up]>=x:
            return lo+1
        else:
            return up+1
s=0
for i in range(n-2):
    a1=l[i]
    for j in range(i+1,n-1):
        k=a1+l[j]
        s=s+nibuta(l[j+1:],k)
print(s)
### BUGGY CODE ###

from collections import deque
from itertools import count
N = int(input())
Ass = [deque(map(int, input().split())) for _ in range(N)]


pairs = deque()
dp = [0 for _ in range(N)]
flag = True
while flag:
    flag = False
    for i, As in enumerate(Ass):
        if not As:
            continue
        t = As[0] - 1
        if Ass[t][0] == i + 1:
            Ass[t].popleft()
            As.popleft()
            dp[t] = dp[i] = max(dp[t], dp[i]) + 1
            flag = True
if any(Ass):
    print(-1)
else:
    print(max(dp))

### FIXED CODE ###

from collections import deque
 
N = int(input())
Ass = tuple(deque(map(int, input().split())) for _ in range(N))
 
dp = [0 for _ in range(N)]
Q = set(range(N))
ans = -1
while Q:
    ans += 1
    Q2 = Q.copy()
    Q.clear()
    for i in Q2:
        if not Ass[i]:
            continue
        t = Ass[i][0] - 1
        if not Ass[t]:
            continue
        if Ass[t][0] == i + 1:
            Q.add(i)
            Q.add(t)
    for i in Q:
        Ass[i].popleft()

if any(Ass):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

s=input()
q=int(input())
for i in range(q):
  t=input()
  if t=='1':
    s=s[::-1]
  else:
    t, f, c = map(str, t.split())
    if f =='1':
      s=c+s
    else:
      s=s+c
print(s)

### FIXED CODE ###

s=input()
q=int(input())
head=''
foot=''

a=0
for i in range(q):
  t=input()
  if t=='1':
    a=a^1
  else:
    t, f, c = map(str, t.split())
    f=int(f)
    if (f^a)&1==0:
      foot+=c
    else:
      head=c+head
s=head+s+foot
if a==1:
  s=s[::-1]
print(s)
### BUGGY CODE ###

N,K=map(int,input().split())
A=input().split()
balls=[a for a in A]
aballs=[]
for a in balls:
    if a in aballs:
        pass
    else:
        aballs.append(a)
number=len(aballs)
n=number-K
counts=[]
for a in aballs:
    kazu=balls.count(a)
    counts.append(kazu)
newcounts=sorted(counts)
answer=0
for a in range(n):
    answer+=newcounts[a]
print(answer)


### FIXED CODE ###

N,K=map(int,input().split())
A=input().split()
balls=[int(a) for a in A]
answers=[0]*200000
for a in balls:
    answers[a-1]+=1
list=[a for a in answers if a!=0]
newlist=sorted(list)
n=len(newlist)-K
answer=0
for a in range(n):
    answer+=newlist[a]
print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
 
ab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(K)]
 
lstab = [[] for _ in range(N)]
lstcd = [[] for _ in range(N)]
 
for a,b in ab:
    lstab[a-1].append(b-1)
    lstab[b-1].append(a-1)

for c,d in cd:
    lstcd[c-1].append(d-1)
    lstcd[d-1].append(c-1)
    
groups = []
visiteds = [0] * N

for i in range(N):
    if visiteds[i] == 1: continue
    temp = [i]
    visited = [i]
    visiteds[i] = 1
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visiteds[y] == 1:continue
            temp.append(y)
            visited.append(y)
            visiteds[y] = 1
    groups.append(visited)
 
ans = [0] * N
for grp in groups:
    setgrp = set(grp)
    for j in grp:
        ans[j] = len(setgrp - set(lstcd[j])) - 1 - len(lstab[j])
 
print(*ans)

### FIXED CODE ###

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

N, M, K = map(int, input().split())
 
lstab = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    lstab[a-1].append(b-1)
    lstab[b-1].append(a-1)

visited = [0] * N
cnt = 0

for i in range(N):
    if visited[i] != 0: continue
    temp = [i]
    cnt += 1
    visited[i] = cnt
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visited[y] != 0:continue
            temp.append(y)
            visited[y] = cnt

numcd = [ 0 ] * N
for _ in range(K):
    c, d = map(int, input().split())
    if visited[c-1] == visited[d-1]:
        numcd[c-1] += 1
        numcd[d-1] += 1    
    
ans = [0] * N
cnt = Counter(visited)

for i in range(N):
    ans[i] = cnt[visited[i]] - 1 - len(lstab[i]) - numcd[i]
 
print(*ans)
### BUGGY CODE ###

import itertools
N = int(input())
l = list(map(int, input().split()))
L = list(itertools.combinations(l,3))
ans = 0
for a, b, c in L:
    if a < b + c and b < c + a and c < a + b:
        ans += 1
print(ans)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += bisect_left(L, L[i]+L[j])-j-1
print(ans)
### BUGGY CODE ###

a,b,n = map(int,input().split())

max1 = (a*2)//b - a*(2//b)
max2 = (a*(n//2))//b - a*((n//2)//b)


for i in range(2,n//2):
    if (a*i)//b - a*(i//b) >= max1:
        max1 = (a*i)//b - a*(i//b)

for i in range(n//2,n+1):
    if (a*i)//b - a*(i//b) >= max2:
        max2 = (a*i)//b - a*(i//b)

if max1 > max2:
    print(max1)
else:
    print(max2)

### FIXED CODE ###

a,b,n = map(int,input().split())

if n >= b-1:
    x = b-1
else:
    x = n

ans = (a*x)//b - a*(x//b)
print(ans)
### BUGGY CODE ###

from itertools import product

H, W = map(int, input().split())
S = [input() for _ in range(H)]
G = [[float("inf")]*W for _ in range(H)]
G[0][0] = 1

for _, i, j in product(range(H*W), range(H), range(W)) :
    if S[i][j] == "." :
        for x, y in [(1, 0), (0, 1), (-1, 0), (0, -1)] :
            if 0 <= i+x < H and 0<= j+y < W :
                G[i][j] = min(1+G[i+x][j+y], G[i][j])

d = sum(s.count(".") for s in S)
a = d-G[-1][-1]
print(-1 if a==-float("inf") else a)

### FIXED CODE ###

H,W=map(int,input().split());S=[input() for _ in range(H)];G=[[-1]*W for _ in range(H)];G[0][0]=1;q=[(0,0)]
while q:
 i,j=q[0];q=q[1:]
 for x,y in[(1,0),(0,1),(-1,0),(0,-1)]:
  t,u=i+x,j+y
  if 0<=t<H and 0<=u<W and G[t][u]<0 and S[t][u]==".":
   G[t][u]=1+G[i][j];q+=[(t,u)]
print(-1*(G[-1][-1]<0)or sum(s.count(".")for s in S)-G[-1][-1])
### BUGGY CODE ###

n = int(input())

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

rg = range(1, n + 1)

for i in rg:
    print(ls.count(i))
    if ls.count(i) != 0:
        ls.remove(i)


### FIXED CODE ###

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

ls2 =[0 for x in range(n)]
#0がn個のリストを用意する

for x in ls:
    ls2[x - 1] += 1

for x in range(n):
    print(ls2[x])
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    def main():

        n=int(input())
        d=list(map(int,input().split()))
        m=int(input())
        t=list(map(int,input().split()))
        from collections import Counter
        dd=Counter(d)
        tt=Counter(t)
        ddl=list(dd.keys())
        for x,y in tt.items():
            flag=True
            for j,k in dd.items():
                if x==j :
                    if y<=k:
                        flag=False
                        break
                    else:
                        return 'NO'
            if flag:
                return 'NO'
        return 'YES'
    print(main())
resolve()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    def main():

        n=int(input())
        d=list(map(int,input().split()))
        m=int(input())
        t=list(map(int,input().split()))
        from collections import Counter
        dd=Counter(d)
        tt=Counter(t)
        for key,value in tt.items():
            if dd[key]<value:
                return 'NO'
        return 'YES'
    print(main())
resolve()
### BUGGY CODE ###

N = int(input())
L = [i for i in range(1,N+1)]
print(sum(L[:-1]))

### FIXED CODE ###

N = int(input())
print((N-1)*(1+N-1)//2)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    ans = deque([0] * N)
    con = [[] for i in range(N)]

    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

    for _ in range(Q):
        p, v = map(int, input().split())
        ans[p-1] += v

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stacks.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque

N, Q = map(int, input().split())
edge = [[] for i in range(N)]
ops = []
ans = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
for _ in range(Q):
    ops.append(tuple(map(int, input().split())))

for op in ops:
    node = op[0] - 1
    pnt = op[1]
    ans[node] += pnt

stack = deque()
stack.append((0, -1))

while stack:
    st = stack.pop()
    node, parent = st[0], st[1]
    children = edge[node]
    for child in children:
        if child == parent:
            continue
        ans[child] += ans[node]
        stack.append((child, node))

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

import numpy as np

N = int(input())
X = str(input())
num_one = X.count("1")
def func(x):
    if x == 0:
        return 0
    else:
        counter = 0
        x_tmp = x
        while x > 0:
            if x % 2 == 1:
                counter += 1
            x = x >> 1
        return func(x_tmp % counter) + 1

num_one = X.count("1")
zero_ver = np.array([pow(2,  i, num_one + 1) for i in range(N)])
one_ver = np.array([-1])
if num_one != 1:
    one_ver = np.array([pow(2,  i, num_one - 1) for i in range(N)])
bool_arr = np.array([True if X[N-i-1] == "1" else False for i in range(N)])
for i in range(1,N+1):
    tmp_bool = bool_arr.copy()
    start = 0
    if tmp_bool[N-i] == False:
        tmp_bool[N-i] = True
        start = sum(zero_ver[tmp_bool]) % (num_one + 1)
        print(func(start)+1)
    else:
        if sum(one_ver) == -1:
            print(0)
        else:
            tmp_bool[N-i] = False
            start = sum(one_ver[tmp_bool]) %  (num_one - 1)
            print(func(start)+1)

### FIXED CODE ###

import numpy as np

N = int(input())
X = str(input())
num_one = X.count("1")

dp = [-1] * N
dp[0] = 0
def dfs(n):
    if dp[n] == -1:
        dp[n] = 1 + dfs(n % bin(n).count('1'))
    return dp[n]

num_one = X.count("1")
bool_arr = np.array([True if X[N-i-1] == "1" else False for i in range(N)])
zero_ver = np.array([pow(2,  i, num_one + 1) for i in range(N)])
zero_ver_sum = sum(zero_ver[bool_arr])

one_ver = -1
one_ver_sum = 0
flag = False
if num_one != 1:
    one_ver = np.array([pow(2,  i, num_one - 1) for i in range(N)])
    one_ver_sum = sum(one_ver[bool_arr])
else:
    flag = True
for i in range(1,N+1):
    start = 0
    if bool_arr[N-i] == False:
        start = (zero_ver_sum + pow(2, N - i, num_one + 1)) % (num_one + 1)
        print(dfs(start)+1)
    else:
        if flag:
            print(0)
        else:
            start = (one_ver_sum - pow(2, N - i, num_one - 1))  %  (num_one - 1)
            print(dfs(start)+1)
### BUGGY CODE ###

h, w = input().split()
h = int(h)
w = int(w)
field = []
for _ in range(h):
    field.append(input())

ans = True
for i in range(h):
    for j in range(w):
        if field[i][j] == '#':
            temp = 0
            que = list()
            que.append((i, j))
            while que:
                x, y = que.pop(0)
                temp += 1
                string = list(field[x])
                string[y] = '.'
                field[x] = ''.join(string)
                dd = [(1, 0), (-1, 0), (0, 1), (0, -1)]
                for ddd in dd:
                    dx, dy = ddd
                    nx, ny = x + dx, y + dy
                    if nx >= 0 and nx < h and ny >= 0 and ny < w and field[nx][ny] == '#':
                        que.append((nx, ny))
            if temp == 1:
                ans = False
                break

if ans:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

h, w = input().split()
h = int(h)
w = int(w)
field = []
for _ in range(h):
    field.append(input())
    
ans = True
for i in range(h):
    for j in range(w):
        if field[i][j] == '#':
            temp = 1
            dd = [(1, 0), (-1, 0), (0, 1), (0, -1)]
            for ddd in dd:
                dx, dy = ddd
                nx, ny = i + dx, j + dy
                if nx >= 0 and nx < h and ny >= 0 and ny < w and field[nx][ny] == '#':
                    temp += 1
            if temp == 1:
                ans = False
                break

if ans:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

# 15:20
n = int(input())
s = []
ans = 0
for i in range(n):
    t = sorted(input())
    ans += s.count(t)
    s.append(t)
print(ans)

### FIXED CODE ###

# 15:20 -16:08 giveup
# 21:45 -22:33 review
from collections import Counter

# 3
# acornistnt
# peanutbomb
# constraint
n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
# s is ['acinnorstt', 'abbemnoptu', 'acinnorstt']
counter = Counter(s)
# counter is Counter({'acinnorstt': 2, 'abbemnoptu': 1})
# counter.values() is dict_values([3, 2])
ans = sum(x*(x-1)//2 for x in counter.values())
print(ans)
### BUGGY CODE ###

N=int(input())
S=input()
R=[]
G=[]
B=[]
for i in range(N):
  if S[i]=='R':
    R.append(i)
  elif S[i]=='G':
    G.append(i)
  else:
    B.append(i)

cnt=0
for i in R:
  for j in G:
    for k in B:
      a=max(i,j,k)
      b=min(i,j,k)
      c=i+j+k-a-b
      if a-c!=c-b:
        cnt+=1
print(cnt)

### FIXED CODE ###

N=int(input())
S=input()
R=[]
G=[]
B=[]
for i in range(N):
  if S[i]=='R':
    R.append(i)
  elif S[i]=='G':
    G.append(i)
  else:
    B.append(i)

cnt=len(R)*len(G)*len(B)
for i in R:
  for j in G:
    if (i+j)%2==0 and S[(i+j)//2]=='B':
      cnt-=1
for i in R:
  for j in B:
    if (i+j)%2==0 and S[(i+j)//2]=='G':
      cnt-=1
for i in B:
  for j in G:
    if (i+j)%2==0 and S[(i+j)//2]=='R':
      cnt-=1      
print(cnt)
### BUGGY CODE ###


import math
n,a,b,k= map(int,input().split())	
w = []


w = [1]
for i in range(0,n):
    w.append(w[-1]*(n-i)//(i+1))
#コンビネーション


c = 0
if k//a >= n:
    x = n
else:
    x = k //a

if k == 0:
    c = 1   
else:
    for h in range(0,x+1):
        i = (k-a*h)/b
    
        if i == int(i) and n >= i:
            c = w[h]*w[int(i)]%998244353+c

print(c%998244353)

### FIXED CODE ###

mod = 998244353

n,a,b,k = map(int,input().split())

fact = [1]
fact_inv = [1]
for i in range(n+4):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))


def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod


res = 0

for i in range(n+1):
    if k - a*i < 0:
        continue
    
    if (k-a*i)%b != 0:
        continue

    j = (k-a*i)//b

    if j > n:
        continue

    res = (res + mod_comb_k(n,j,mod)*mod_comb_k(n,i,mod)%mod)%mod

print(res%mod)
### BUGGY CODE ###

N=int(input())
S=list(map(int, input().split()))
ans=0
for i in range(0,N):
  
  if min(S[:i+1])==S[i]:
    ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=list(map(int, input().split()))
Min=2*(10**5)
ans=0
for i in S:
  if Min>=i:
    Min=i
    ans+=1
    
print(ans)
### BUGGY CODE ###

import copy
n,k,*A = map(int,open(0).read().split())

for _ in range(k):
    C = [0] * n
    for i,d in enumerate(A):
        for j in range(i-d,i+d+1):
            if 0<=j<n:
                C[j] += 1
    A = copy.deepcopy(C)

print(*C)


### FIXED CODE ###

import copy
n,k,*A = map(int,open(0).read().split())
for _ in range(min(50,k)):
    B = [0] * (n+1)
    for i,d in enumerate(A):
        start = max(0,i-d)
        B[start] += 1
        end = min(n,i+d+1)
        B[end] -= 1
    light = 0 
    for i,b in enumerate(B[:n]):
        light += b
        A[i] = light

print(*A)
### BUGGY CODE ###

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

l = sorted(l, reverse = True)

ans = []
for i in range(len(l)-2):
    for j in range(len(l)-2-i):
        if l[i] > 2 * l[i+j+1]:
            break
        for k in range(len(l)-2-i-j):
            if l[i] < l[i+j+1] + l[i+j+k+2]:
                if [l[i], l[i+j+1], l[i+j+k+2]] not in ans:
                    ans.append([l[i], l[i+j+1], l[i+j+k+2]])
            else:
                break

print(len(ans))
    

         
        
        
    

        
            
        
    
        




### FIXED CODE ###

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

l.sort(reverse=True)
ans = 0
for i in range(n-2):
    j = i+1
    k = n-1
    while (j < k):
        if l[i] - l[j] - l[k] < 0:
            ans += k - j
            j += 1
        else:
            k -= 1

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

#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import sys

lim=10**9+7
N,M = map(int,input().split())
A=[]
for i in range(0,M):
    A.append(int(input()))

memo = [0] * (N+1)
memo[0]=1
if not 2 in A:
    memo[1]=1
for i in range(2, N+1):
    if not i in A:
        if not ((i-1 in A) or (i-2 in A)):
            memo[i] = (memo[i - 1] + memo[i - 2]) % lim
        elif i-1 in A:
            memo[i] = memo[i - 2]
        elif i-2 in A:
            memo[i] = memo[i - 1]
        elif (i-1 in A) and (i-2 in A):
            print(0)
            sys.exit()
print(memo[-1])

### FIXED CODE ###

#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import sys

lim=10**9+7
N,M = map(int,input().split())
A = set([int(input()) for _ in range(M)])
memo = [0] * (N+1)
memo[0]=1

if not 1 in A:
    memo[1]=1
for i in range(2, N+1):
    if not i in A:
        memo[i] = (memo[i - 1] + memo[i - 2]) % lim
print(memo[-1])
### BUGGY CODE ###

S = int(input())
Smod = [0]*2019
for i in range(len(str(S))+1):
  Smod[(S%(10**i))%2019] += 1

ans = 0
for j in range(2019):
  ansj = Smod[j]
  ans += ansj * (ansj-1) // 2
print(ans)

### FIXED CODE ###

S = input()
Sliststr = list(S)
Slist = [int(s) for s in Sliststr]
Smod = [0]
mod10 = [1]
count = [0]*2019
ans = 0
for i in range(len(S)-1):
  mod10.append(mod10[i]*10%2019)
for i in range(len(S)):
  Smod.append((Smod[i]+Slist[-i-1]*mod10[i])%2019)
for i in range(len(Smod)):
  count[Smod[i]] += 1
for i in range(2019):
  ans += count[i] * (count[i]-1) // 2
print(ans)