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

N, M = map(int, input().split())
L = [list(input().split()) for i in range(M)]
AC = list(set([L[j][0] for j in range(M) if L[j][1] == 'AC']))
P = 0
for k in AC:
  n = L.index([k, 'AC'])
  P += L[:n].count([k, 'WA'])
print(len(AC), P)

### FIXED CODE ###

N, M = map(int, input().split())
P = [0] * (N + 1)
S = [0] * (N + 1)
for i in range(M):
  x, p = input().split()
  s = int(x)
  if P[s] == 0:
    if p == 'AC':
      P[s] = 1
    else:
      S[s] += 1
A = sum([S[i] for i in range(N + 1) if P[i] == 1])
print(P.count(1), A)
### BUGGY CODE ###

def e_bomber():
    from collections import defaultdict
    H, W, M = [int(i) for i in input().split()]

    bomb_row = [0] * H
    bomb_col = [0] * W
    bomb_pos = defaultdict(int)
    for _ in range(M):
        r, c = [int(i) - 1 for i in input().split()]
        bomb_row[r] += 1
        bomb_col[c] += 1
        bomb_pos[(r, c)] += 1

    bomb_row_max = max(bomb_row)
    bomb_col_max = max(bomb_col)

    # 破壊できる数が最大になるような行と列の組を全探索する。
    # (行, 列) が破壊対象の上になってしまわないような組があれば、そこに置けばいい。
    # そのような組がまったくなければ、破壊対象の上に置かざるを得ない (-1 される)。
    flag = False
    for row in [r for r in range(H) if bomb_row_max == bomb_row[r]]:
        for col in [c for c in range(W) if bomb_col_max == bomb_col[c]]:
            if bomb_pos[(row, col)] == 0:
                return bomb_row_max + bomb_col_max
    return bomb_row_max + bomb_col_max - 1

print(e_bomber())

### FIXED CODE ###

def e_bomber():
    import sys
    input = sys.stdin.readline

    H, W, M = [int(i) for i in input().split()]

    bomb_row = [0] * H
    bomb_col = [0] * W
    bomb_pos = set()
    for _ in range(M):
        r, c = [int(i) - 1 for i in input().split()]
        bomb_row[r] += 1
        bomb_col[c] += 1
        bomb_pos.add((r, c))

    bomb_row_max = max(bomb_row)
    bomb_col_max = max(bomb_col)
    row_index_list = [r for r, v in enumerate(bomb_row) if v == bomb_row_max]
    col_index_list = [c for c, v in enumerate(bomb_col) if v == bomb_col_max]

    # 破壊できる数が最大になるような行と列の組を全探索する。
    # (行, 列) が破壊対象の上になってしまわないような組があれば、そこに置けばいい。
    # そのような組がまったくなければ、破壊対象の上に置かざるを得ない (-1 される)。
    for row in row_index_list:
        for col in col_index_list:
            if (row, col) not in bomb_pos:
                return bomb_row_max + bomb_col_max
    return bomb_row_max + bomb_col_max - 1

print(e_bomber())
### BUGGY CODE ###

from collections import Counter

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

ans = 0
while len(A.keys()) > K:
  min_key = [key for key in A if A[key] == min(A.values())][0]
  ans += A[min_key]
  del A[min_key]
print(ans)

### FIXED CODE ###

from collections import Counter

N,K = map(int,input().split())
A = Counter(list(map(int,input().split())))
nums = sorted(A.values(), reverse= True)
num = len(nums)
ans = 0

while num > K:
  ans += nums[-1]
  del nums[-1]
  num -= 1
print(ans)
### BUGGY CODE ###

def main():
    # import sys
    # readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    from collections import deque

    A = input()
    N = len(A)
    a = ord('a')

    INF = N
    na = [[INF] * 26 for _ in range(N)]
    for i in range(N - 1, -1, -1):
        c = ord(A[i]) - ord('a')
        for j in range(26):
            na[i][j] = i if c == j else na[(i + 1) % N][j]

    q = deque()
    q.append(([], -1))

    while q:
        s, i = q.popleft()
        for j in range(26):
            ni = na[i + 1][j]
            ns = s + [chr(a + j)]
            if ni == INF:
                print(''.join(ns))
                exit()
            else:
                q.append((ns, ni))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    # import sys
    # readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    
    A = input()
    N = len(A)
    a = ord('a')

    INF = N
    na = [[INF] * 26 for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        c = ord(A[i]) - a
        for j in range(26):
            na[i][j] = na[i + 1][j]
        na[i][c] = i

    dp = [INF] * (N + 1)
    dp[N] = 1
    recon = [None] * (N + 1)
    for i in range(N - 1, -1, -1):
        for j in range(26):
            ni = na[i][j]
            if ni == N:
                if dp[i] > 1:
                    dp[i] = 1
                    recon[i] = (chr(a + j), N)
            elif dp[i] > dp[ni + 1] + 1:
                dp[i] = dp[ni + 1] + 1
                recon[i] = (chr(a + j), ni + 1)

    # k =
    # for j in range(26):
    #     ni = na[0][j]
    #     if dp[i] > dp[ni] + 1:

    i = 0
    ans = []
    while i < N:
        c, ni = recon[i]
        ans.append(c)
        i = ni

    print(''.join(ans))


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

L , R = map(int,input().split())

ans = float('inf')

for i in range(L, R+1) :
    for j in range(i+1,min(R+1,i+2020)) :
        ans = min(ans, (i*j) % 2019)

print(ans)

### FIXED CODE ###

L , R = map(int,input().split())

ans = float('inf')

for i in range(L, min(R+1,L+2020)) :
    for j in range(i+1,min(R+1,i+2020)) :
        ans = min(ans, (i*j) % 2019)

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

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

ans = 0

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if a[i] % a[j] == 0:
            break
    else:
        ans += 1

print(ans)

### FIXED CODE ###

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

m = 10 ** 6 + 7

count = [0] * m

for x in a:
    if count[x] != 0:
        count[x] = 2
        continue

    for i in range(x, m, x):
        count[i] += 1

ans = 0
for x in a:
    if count[x] == 1:
        ans += 1

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

from collections import deque
N=int(input())
uvw=list(list(map(int,input().split())) for _ in range(N-1))

graph=[[0]*N for _ in range(N)]
for u,v,w in uvw:
    graph[u - 1][v - 1] = w
    graph[v - 1][u - 1] = w
colors=[2]*N
queue=deque([0])
colors[0]=0
while len(queue)>0:
    x=queue.popleft()
    if all(colors[h]!=2 for h in range(N)):
        break
    for j in range(N):
        if colors[j]==2 and graph[x][j]!=0:
            queue.append(j)
            colors[j]=(colors[x]+graph[x][j])%2
for p in colors:
    print(p)


### FIXED CODE ###

from collections import deque
N=int(input())
uvw=list(list(map(int,input().split())) for _ in range(N-1))

graph_list=[[] for _ in range(N)]
for u,v,w in uvw:
    graph_list[u - 1].append([v,w])
    graph_list[v - 1].append([u,w])

colors=[-1]*N
colors[0]=0
queue=deque([1])

while len(queue)>0:
    x=queue.popleft()
    if all(colors[i]!=-1 for i in range(N)):
        break
    for j in graph_list[x-1]:
        if colors[j[0]-1]==-1:
            queue.append(j[0])
            colors[j[0]-1]=(2+colors[x-1]+j[1])%2
for p in colors:
    print(p)
### BUGGY CODE ###

from collections import defaultdict
S = list(map(int,list(input())))
N = len(S)
ans = 0
pre_d = defaultdict(int)
for i in range(N):
    new_d = defaultdict(int)
    for k, v in pre_d.items():
        new_d[(10 * k + S[i]) % 2019] += v
    new_d[S[i]] += 1
    ans += new_d[0]
    pre_d = new_d
print(ans)

### FIXED CODE ###

from collections import Counter

S = list(map(int,list(input())))
S.reverse()
N = len(S)
L = [0]
power = 1
for i in range(N):
    L.append((L[-1] + S[i] * power) % 2019)
    power *= 10
    power %= 2019
count = Counter(L)
ans = 0
for value in count.values():
    ans += value * (value - 1) // 2
print(ans)
### BUGGY CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	#b , c = IN()
	c=0
	s = input()
	
	ll=len(s)
	for i in range(ll):
		for j in range(i+1, ll+1):
			#print(s[i:j])
			if int(s[i:j]) % 2019 == 0:
				#print(i,j,s[i:j])
				c+=1
	print(c)
				
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main2():
	#a = int(input())
	#b , c = IN()
	s =  input()
	#s='1'*3000
	s=[int(c) for c in s]
	ll=len(s)
	ret_count=0
	for i in range(1):#ll-2):
		v = s[i]
		vs=[v]
		for c in s[i+1:]:
			v = (v * 10 + c) % 2019
			vs.append(v)
			if v == 0:
				ret_count += 1
		else:
			pa(vs)	
	print(ret_count)
				
def main():
	#a = int(input())
	#b , c = IN()
	s =  input()
	#s='1'*3000
	s=[int(c) for c in s]
	s=s[::-1]
	ll=len(s)
	cc=[0]*2019
	p=0
	tt=1
	cc[0]=1
	for i, v in enumerate(s):
		tt *= 10
		tt %= 2019
		p += tt*v
		p %= 2019
		cc[p] += 1
	
	ret = 0
	for v in cc:
		ret += v *(v-1)//2
	print(ret)	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
ans = []
kitaiti = 0
for i in range(len(p)):
    ans.append(sum(p[i:i+k]))
key = ans.index(max(ans))
ans_list = p[key:key+k]
for i in ans_list:
    kitaiti += (((1+i)/2)*i)*i**-1
print(kitaiti)


### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
p_kitaiti = [(1+p[i])/2 for i in range(n)]
ans = sum(p_kitaiti[:k])
number = sum(p_kitaiti[:k])
for i in range(k,n):
    number = number + p_kitaiti[i] - p_kitaiti[i-k]
    ans = max(ans,number)
print(ans)
### BUGGY CODE ###

def solve():
    N = int(input())
    a = list(map(int, input().split()))
    ans = 0
    check = 0
    checkmm = 0
    checkm = 0
    a.sort()
    for i in a:
        if i == i-1:
            break
        if i-2 in a:
            checkmm = checkm
        else:
            checkmm = 0

        if i-1 in a:
            checkm = check
        else :
            checkm = 0

        check = a.count(i)


        if ans < check+checkm+checkmm:
            ans = check+checkm+checkmm

    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N = int(input())
    a = list(map(int, input().split()))
    count = [0]*100000

    for i in a:
        count[i] += 1

    print(max(map(sum,zip(count,count[1:],count[2:]))))


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

import sys
sys.setrecursionlimit(10**6)
N = int(input())
*A, = map(int, input().split())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

def calc(S):
    if not S:
        return 0
    S.sort(reverse=1)
    if S[0] > sum(S[1:]):
        return sum(S[1:])
    return sum(S)//2
ok = 1
def dfs(v, p):
    global ok
    c = A[v]
    S = []
    for w in G[v]:
        if w == p:
            continue
        S.append(dfs(w, v))
    if not S:
        return c
    d = calc(S)
    s = sum(S)
    k = s - c
    if not 0 <= k <= d:
        ok = 0
    return s - 2*k
import random
random.seed()
*r, = range(N)
random.shuffle(r)
d = {}
for i in range(min(3, N)):
    dfs(r[i], -1)

if ok:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
*A, = map(int, input().split())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

def calc(S):
    if not S:
        return 0
    S.sort(reverse=1)
    if S[0] > sum(S[1:]):
        return sum(S[1:])
    return sum(S)//2
ok = 1
def dfs(v, p):
    global ok
    c = A[v]
    S = []
    for w in G[v]:
        if w == p:
            continue
        S.append(dfs(w, v))
    if not S:
        return c
    d = calc(S)
    s = sum(S)
    k = s - c
    if not 0 <= k <= d:
        ok = 0
    return s - 2*k
import random
random.seed()
*r, = range(N)
random.shuffle(r)
d = {}
for i in range(2):
    dfs(r[i], -1)

if ok:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

S = input()
P = [0 for _ in range(len(S)+1)]
mod = 2019
d = 1
for i in range(len(S), 0, -1):
    P[i-1] = int(S[i-1])*d + P[i]
    P[i-1] = P[i-1] % mod
    d *= 10

A = [0 for _ in range(2019)]
for p in P:
    A[p] += 1

ans = sum(list(map(lambda n: n*(n-1)//2, A)))
print(ans)

### FIXED CODE ###

from collections import Counter
S = input()
P = [0] * (len(S)+1)
mod = 2019
d = 1
for i in range(len(S), 0, -1):
    P[i-1] = int(S[i-1])*d + P[i]
    P[i-1] = P[i-1] % mod
    d *= 10
    d = d % mod

P = Counter(P)
ans = 0
for p in P.values():
    ans += p*(p-1)//2
print(ans)
### BUGGY CODE ###

from math import ceil, log2


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.aggfunc = aggfunc
        self.depth = ceil(log2(length))
        self.data = [init_value] * (2 ** (1 + self.depth) - 1)
        self.origin = 2 ** self.depth - 1

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break


n, q = map(int, input().split())
stx = [map(int, input().split()) for _ in range(n)]
d = [int(input()) for _ in range(q)]
xs = set()
events = []

for s, t, x in stx:
    events.append((s - x, 1, x))
    events.append((t - x, -1, x))
    xs.add(x)
events.sort()

xs = list(xs)
xs.sort()


zaatsu = dict(zip(xs, range(len(xs))))

ub = 10 ** 9 + 1
koujichu = SegmentTree(len(zaatsu), ub, min)

i = 0
for di in d:
    while i < len(events) and events[i][0] <= di:
        if events[i][1] == 1:
            koujichu.update(zaatsu[events[i][2]], events[i][2])
        else:
            koujichu.update(zaatsu[events[i][2]], ub)
        i += 1
    if koujichu.data[0] != ub:
        print(koujichu.data[0])
    else:
        print(-1)


### FIXED CODE ###

import sys
from bisect import bisect_left

input = sys.stdin.readline
n, q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

stx.sort(key=lambda x: x[2])

ans = [-1] * q
jump = [-1] * q
for s, t, x in stx:
    d_start = bisect_left(d, s - x)
    d_stop = bisect_left(d, t - x, lo=d_start)
    while d_start < d_stop:
        if jump[d_start] == -1:
            ans[d_start] = x
            jump[d_start] = d_stop
            d_start += 1
        else:
            d_start = jump[d_start]

for an in ans:
    print(an)
### BUGGY CODE ###

from itertools import accumulate


def dfs(l, r):
    if memo[l][r]:
        return dp[l][r]
    for i in range(l, r):
        dp[l][r] = min(max(0, dp[l][r]), dfs(l, i) + dfs(i + 1, r) + acc_A[r] - acc_A[l - 1])
    memo[l][r] = True
    return dp[l][r]


n = int(input())
A = list(map(int, input().split()))
acc_A = [0] + list(accumulate(A))

INF = 10 ** 18
dp = [[INF] * (n + 1) for _ in range(n + 1)]
memo = [[False] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    dp[i][i] = 0
    memo[i][i] = True


print(dfs(1, n))


### FIXED CODE ###

from itertools import accumulate


def dfs(l, r):
    if memo[l][r]:
        return dp[l][r]
    for i in range(l, r):
        dp[l][r] = min(max(0, dp[l][r]), dfs(l, i) + dfs(i + 1, r) + acc_A[r] - acc_A[l - 1])
    memo[l][r] = True
    return dp[l][r]


n = int(input())
A = list(map(int, input().split()))
acc_A = [0] + list(accumulate(A))

INF = 10 ** 18
dp = [[INF] * (n + 1) for _ in range(n + 1)]
memo = [[False] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    dp[i][i] = 0
    memo[i][i] = True


print(dfs(1, n))
### BUGGY CODE ###

#A1~Aiまでの和 O(logN)　iが与えられたとき a1~aiまでの和を計算する(O(log n))
def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

#Ai+=x O(logN)　iとxが与えられたとき ai+=x とする (O(log n))
def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

N,Q=map(int, input().split())
C=list(map(int, input().split()))
LRI=[]
for i in range(Q):
  l,r=map(int,input().split())
  LRI.append((r,l,i))

LRI.sort(key=lambda x:x[0])
lastAppend =[-1]*(N+1)
#A1 ... AnのBIT(1-indexed)
BIT=[0]*(N+1)
ANS=[0]*Q
now=1
for r,l,i in LRI:
  while now<=r:
    c=C[now-1]
    #初めてその種類が登場
    if lastAppend[c]==-1:
      BIT_update(BIT,now,1,N)
    #その種類の登場が2回目　
    else:
      BIT_update(BIT,now,1,N)
      BIT_update(BIT,lastAppend[c],-1,N)
    lastAppend[c]=now                
    now+=1
  ANS[i]=BIT_query(BIT,r)-BIT_query(BIT,l-1)

for ans in ANS:
  print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

def main():
  N,Q=map( int, input().split())
  C=list( map( int, input().split()))
  LRI=[]
  for i in range(Q):
    l,r=map( int, input().split())
    LRI.append((r,l,i))
  LRI.sort(key=lambda x:x[0])
  lastAppend=[-1]*(N+1)
  BIT=[0]*(N+1)
  ANS=[0]*Q
  now=1
  for r,l,i in LRI:
    while now <= r:
      c=C[now-1]
      if lastAppend[c]== -1:
        BIT_update(BIT,now,1,N)
      else:
        BIT_update(BIT,now,1,N)
        BIT_update(BIT,lastAppend[c],-1,N)
      lastAppend[c]=now                
      now+=1
    ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
  for ans in ANS:
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
c = [0]*4
for x in map(int, input().split()):
    c[x] += 1
dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]

for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            non_zero = i+j+k
            if non_zero == 0:
                continue
            dp[i][j][k] = n/non_zero
            if 0 <= i-1 and j+1 <= n:
                dp[i][j][k] += dp[i-1][j+1][k]*i/non_zero
            if 0 <= j-1 and k+1 <= n:
                dp[i][j][k] += dp[i][j-1][k+1]*j/non_zero
            if 0 <= k-1:
                dp[i][j][k] += dp[i][j][k-1]*k/non_zero

print(dp[c[3]][c[2]][c[1]])


### FIXED CODE ###

from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]

for i in range(n+1):
    for j in range(n+1-i):
        for k in range(n+1-i-j):
            non_zero = i+j+k
            if non_zero == 0:
                continue
            dp[i][j][k] = n
            if 0 <= i-1 and j+1 <= n:
                dp[i][j][k] += dp[i-1][j+1][k]*i
            if 0 <= j-1 and k+1 <= n:
                dp[i][j][k] += dp[i][j-1][k+1]*j
            if 0 <= k-1:
                dp[i][j][k] += dp[i][j][k-1]*k
            dp[i][j][k] /= non_zero

print(dp[c[3]][c[2]][c[1]])
### BUGGY CODE ###

n,k = map(int,input().split())
MOD = 10**9+7

history = {}
def comb(n,k):
  if (n,k) in history:
    return history[(n,k)]
  res = 1
  for i in range(k):
    res *= n-i
    res *= pow(i+1,MOD-2,MOD)
    res = res % MOD
  history[(n,k)] = res
  history[(n,n-k)] = res
  return res

for i in range(k):
  #print(comb(k-1,i),comb(n-k+1,i+1))
  ans = comb(k-1,i) * comb(n-k+1,i+1)
  print(ans % MOD)



### FIXED CODE ###

n,k = map(int,input().split())
MOD = 10**9+7

history = {}
def comb(n,k):
  if (n,k) in history:
    return history[(n,k)]
  if k == 0:
    return 1
  res = (n-k+1)*pow(k,MOD-2,MOD)*comb(n,k-1)
  res = res%MOD
  history[(n,k)] = res
  history[(n,n-k)] = res
  return res

for i in range(k):
  #print(comb(k-1,i),comb(n-k+1,i+1))
  ans = comb(k-1,i) * comb(n-k+1,i+1)
  print(ans % MOD)
### BUGGY CODE ###

import bisect


def main():
    n = int(input())
    l_lst = list(map(int, input().split()))
    l_lst.sort()

    count = 0
    for i in range(n - 1):
        for j in range(i + 1, n):

            lst = l_lst[j + 1:]
            a = l_lst[i]
            b = l_lst[j]
            count += bisect.bisect(lst, a + b - 1)

    print(count)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect


def main():
    n = int(input())
    l_lst = list(map(int, input().split()))
    l_lst.sort()

    count = 0
    for i in range(n - 1):
        for j in range(i + 1, n):

            a = l_lst[i]
            b = l_lst[j]
            tmp = bisect.bisect_left(l_lst, a + b)
            tmp -= j + 1
            tmp = max(0, tmp)
            count += tmp

    print(count)


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

n, *a = map(int, open(0).read().split())
ans = 0
mod = 10 **9 + 7
for k in range(61):
	m = 1 << k
	c = 0
	for x in a:
		if m & x:
			c += 1
	ans +=c * (n - c) * m
	ans %= mod
print(ans)

### FIXED CODE ###

n, *a = map(int, open(0).read().split())
ans = 0
mod = 10 **9 + 7
for k in range(61):
	m = 1 << k
	c = 0
	for x in a:
		if m & x:
			c += 1
	ans +=c * (n - c) * m
	ans %= mod
print(ans)
### BUGGY CODE ###

H, W = map(int,input().split())
S_ = ["#"]*(W+2)
S = [["#"]+list(input())+["#"] for i in range(H)]
S = [S_] + S + [S_]

L_cnt = [[0]*(W+2) for i in range(H+2)]
R_cnt = [[0]*(W+2) for i in range(H+2)]
U_cnt = [[0]*(W+2) for i in range(H+2)]
D_cnt = [[0]*(W+2) for i in range(H+2)]

for h in range(1,H+1):
    for w in range(W,0,-1):
        if S[h][w] == ".":
            L_cnt[h][w] = L_cnt[h][w+1]+1

for h in range(1,H+1):
    for w in range(1,W+1,1):
        if S[h][w] == ".":
            R_cnt[h][w] = R_cnt[h][w-1]+1

for w in range(1,W+1):
    for h in range(H,0,-1):
        if S[h][w] == ".":
            U_cnt[h][w] = U_cnt[h+1][w]+1

for w in range(1,W+1):
    for h in range(1,H+1,1):
        if S[h][w] == ".":
            D_cnt[h][w] = D_cnt[h-1][w]+1

ans = 0
for h in range(1,H+1):
    for w in range(1,W+1):
        ans = max(ans,L_cnt[h][w]+R_cnt[h][w]+U_cnt[h][w]+D_cnt[h][w])

print(ans-3)

### FIXED CODE ###

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

yoko = [[0]*W for _ in range(H)]
tate = [[0]*W for _ in range(H)]

def f(l):
    print("\n".join("".join(map(str, row)) for row in l))

for h in range(H):
    if S[h][0] == ".":
        yoko[h][0] = 1
    else:
        yoko[h][0] = 0

for h in range(H):
    for w in range(1, W):
        if S[h][w] == ".":
            yoko[h][w] = yoko[h][w-1]+1
        else:
            yoko[h][w] = 0

for h in range(H):
    for w in range(W-2, -1, -1):
        if S[h][w]=="." and S[h][w+1]==".":
            yoko[h][w] = yoko[h][w+1]

for w in range(W):
    if S[0][w] == ".":
        tate[0][w] = 1
    else:
        tate[0][w] = 0

for w in range(W):
    for h in range(1, H):
        if S[h][w] == ".":
            tate[h][w] = tate[h-1][w]+1
        else:
            tate[h][w] = 0

for w in range(W):
    for h in range(H-2, -1, -1):
        if S[h][w]=="." and S[h+1][w]==".":
            tate[h][w] = tate[h+1][w]

ans = 0

for h in range(H):
    for w in range(W):
        ans = max(yoko[h][w]+tate[h][w]-1, ans)

print(ans)